Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
Contest: Codeforces Round 383 (Div. 1)
Difficulty rating: 2900
Tags: data structures, dfs and similar, trees

Just in case somebody missed it: we have wonderful girls in Arpa’s land.

Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertices are numbered 1 through n, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.

Input format:
The first line contains integer n (1  ≤  n  ≤  5·105) — the number of vertices in the tree.

(n  -  1) lines follow, the i-th of them contain an integer pi + 1 and a letter ci + 1 (1  ≤  pi + 1  ≤  i, ci + 1 is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes pi + 1 and i + 1 and there is a letter ci + 1 written on this edge.

Output format:
Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
4
1 s
2 a
3 s

Example output:
3 1 1 0

Example input:
5
1 a
2 h
1 a
4 h

Example output:
4 1 0 1 0

Editorial:
Please read my dsu on tree (sack) tutorial before you read.
Let’s calculate for each vertex such v, length of longest Dokhtar-kosh path that starts in some vertex of subtree of v, passes from v, and ends in some other vertex of subtree of v using sack (explained below); then we can sum up this values and get answer for each vertex.
First keep a mask for each vertex, i-th bit of maskv is true if the number of edges on the path from the root to v such that the letter i is written on them is odd. Now if the number of bits in $$mask_v \oplus mask_u$$ is 0 or 1, the path between v and u is Dokhtar-kosh.
Let’s use sack, assume bagMask is the maximum height for a vertex that is present in our sack and its mask is equal to Mask.
Let’s define two functions used in sack:
AddToSack(vertex x) : If bagmaskx is less than hx, set bagmaskx = hx.
UpdateCurrentAnswer (vertex x, vertex root) : For each Mask such that $$Mask \oplus mask_x$$ has at most one bit, update the CurrentAnswer, with hx + bagMask - 2·hroot (updating means if CurrentAnswer is less than hx + bagMask - 2·hroot, set CurrentAnswer to it).
Suppose dfs function arrives to vertex v. Call dfs for each child of v except the biggest one (which has more vertices in its subtree than others) and clear the sack each time. Call dfs for big child of v and don’t clear the sack. Then for each other child u and for each vertex $$x \in subTree(u)$$, call UpdateCurrentAnswer(x, v). Then for each vertex $$x \in subTree(u)$$, call AddToSack(x). After the addition of the children is done, call UpdateCurrentAnswer(v, v) and AddToSack(v). Now the answer for this vertex is CurrentAnswer.
To clear the sack, for each vertex $$x \in subTree(v)$$ set bagmaskx =  - inf (i.e.  - 109) and set CurrentAnswer to 0.
Note that there exists another solution using centroid decomposition, but it’s harder.
Time complexity: $${ \mathcal { O } } ( n \cdot \log n \cdot z )$$ (z is number of characters which is equal to 22).
Corner case: You must use an array, no map or unordered map for bag, these solutions got TLE.