Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

baddestguy's blog

By baddestguy, history, 4 years ago, In English

Given a tree with n nodes and n-1 edges, each edge has an integer value that maps to a character from A to Z. For each shortest paths between nodes determine if the sequence of characters of edges encountered can be rearranged to to be palindrome. We are required to count the number of pairs of nodes such that their shortest path can be rearranged to palindrome. (1<=n<=10^5) and tree diameter is less than 1000. Any ideas given those constraints?

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

I think I have a solution. I'm not sure it's correct. It doesn't use the fact that the tree diameter is less than $$$1000$$$.
1. Run the centroid decomposition algorithm.
2. Look through all the paths from this cetroid.
3. For each path, compute the value $$$d[i]$$$, this number will use the first $$$26$$$ bits.
For each path, calculate $$$ctr[26]$$$ (how many times this letter occurs on the path).
For all $$$j \in [0; 25]$$$, put $$$1$$$ in the bit number $$$j$$$ of the number $$$d[i]$$$, if $$$ctr[j]\mod 2 = 1$$$.
Simply, for each path, we store a bitmask, in the $$$i$$$ bit of which we store information about whether the number is even or odd once this letter occurs on the way.
4. Go through all the vertices available from this centroid. And for each one, we update the answer as follows:
1) Let us now be at the vertex $$$v$$$.
2) Since a single letter can occur an odd number of times in a palindrome (the length of the palindrome is odd), we must iterate over the $$$j$$$ bit and find all such $$$d[i]$$$ such that
$$$d[v] \cap 2^j \neq d[i] \cap 2^j$$$. ($$$d[i] = d[v] \oplus 2^j$$$)
All other bits except $$$j$$$ must be the same.
You can calculate the number of such $$$d[i]$$$ using map.
It is also important to consider the case when $$$d[v] = d[i]$$$ (palindrome of even length).
3) IMPORTANT! When considering a vertex $$$v$$$, we should not count those vertices that are in the same subtree with $$$v$$$. But we will return them back when we move to another subtree.
To do this, you can first subtract all d from the subtree of vertex $$$v$$$ from our map structure.
The final asymptotics: $$$O(26n\log^2n)$$$