Blog entries - Codeforces

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	143
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	maroonrk	133
9	BledDest	132
10	qwexd	129

Motivation

I spent hours on 914E - Palindromes in a Tree and finally solved it around 3 AM. The editorial was too short for me to follow, so here's my own version of the idea. Hopefully it's clearer for anyone else stuck on this. I apologize if my english is unclear.

Prerequisites

DFS, bitmasks, Centroid Decomposition.

Hints

Hint 1

What makes a path palindromic?

Answer

The parity of letters. There should be at most one letter that appears odd number of times in this path. Since there are only $$$20$$$ letters, we can store bitmask — $$$i^{\text{th}}$$$ bit represents the parity of $$$i^{\text{th}}$$$ letter. Then, there are only $$$21$$$ valid masks (all bits off, or exactly one of the $$$20$$$ bits on).

Hint 2

How can you check all paths in constant time each, after a single DFS?

Answer

In DFS, store $$$mask_x$$$ — the bitmask of the path from root to $$$x$$$ — for each node. To get the bitmask of path $$$u$$$ $$$\leftrightarrow$$$ $$$v$$$, you can just XOR $$$mask_u$$$ and $$$mask_v$$$ and add the bit for $$$lca(u, v)$$$.

Hint 3

Try to solve the problem in $$$O(N^2)$$$ using previous hints. How can you improve that solution to a full one?

Answer

A slower solution is to check every path and mark valid tuples of $$$u$$$, $$$v$$$, and $$$lca(u, v)$$$. To calculate the answer, you can propagate the marks from child to parent in DFS. To make this solution faster, use Centroid Decomposition.

Solution

Reveal

Read hints first.

Centroid decomposition gives us the advantage of dividing the tree into multiple components, so we can afford to run naive operations within each one — the overall complexity still stays low. Thus, we can alter the logic of the naive solution a little bit and try to find this for each node $$$u$$$ in the component, where $$$c$$$ is the centroid:
How many paths are there in this component that have $$$u$$$ as one endpoint and pass through $$$c$$$?

We can root the component at $$$c$$$ and calculate bitmasks for nodes in a single DFS. From Hint $$$1$$$, we know there are only $$$21$$$ valid bitmasks. Let's call one of them $$$valid$$$. So, for a fixed $$$u$$$, we need a node $$$v$$$ such that $$$mask_u$$$ $$$\oplus$$$ $$$mask_v$$$ $$$=$$$ $$$valid$$$. We can turn this equation into $$$mask_u$$$ $$$\oplus$$$ $$$valid$$$ $$$=$$$ $$$mask_v$$$. But there is one constaint on $$$v$$$ — it should belong to the subtree of a different child of $$$c$$$ than $$$u$$$ belongs to — so the path passes through $$$c$$$. The variety of $$$v$$$ candidates is tight (only $$$21$$$ bitmasks can match with that of $$$u$$$). We can keep count of bitmasks, then add count of $$$mask_u$$$ $$$\oplus$$$ $$$valid$$$ from other subtrees to our answer. Since the path $$$u$$$ — $$$c$$$ — $$$v$$$ also passes through some $$$w$$$ that is an ancestor of $$$u$$$ (rooted at $$$c$$$), we need to update its answer too. We can use propagation from child to parent here — keep the count on $$$u$$$, and when returning to parent inside DFS call, move that count to the parent, and so on. One thing left is the count of paths that have $$$c$$$ as endpoint. We can count them inside the DFS call. That is just the number of nodes with an already valid bitmask.

Overall complexity is $$$O(NlogN)$$$ — each node is traversed $$$logN$$$ times in Decomposition.

Code

388994243

Closing

I really enjoyed working on this problem — it's a great exercise in centroid decomposition. If this tutorial helped you, upvote! If anything is unclear, I would be happy to answer your questions in the comments.

Full text and comments »

omaralimm's blog

Motivation

Prerequisites

Hints

Solution

Code

Closing