Anagram Paths
Contest: Codeforces Round 562 (Div. 1)
Difficulty rating: 3000
Tags: dp, implementation, trees

Toad Ilya has a rooted binary tree with vertex $$$1$$$ being the root. A tree is a connected graph without cycles. A tree is rooted if one vertex is selected and called the root. A vertex $$$u$$$ is a child of a vertex $$$v$$$ if $$$u$$$ and $$$v$$$ are connected by an edge and $$$v$$$ is closer to the root than $$$u$$$. A leaf is a non-root vertex that has no children.

In the tree Ilya has each vertex has at most two children, and each edge has some character written on it. The character can be a lowercase English letter or the question mark '?'.

Ilya will $$$q$$$ times update the tree a bit. Each update will replace exactly one character on some edge. After each update Ilya needs to find if the tree is anagrammable and if yes, find its anagramnity for each letter. Well, that's difficult to explain, but we'll try.

To start with, a string $$$a$$$ is an anagram of a string $$$b$$$ if it is possible to rearrange letters in $$$a$$$ (without changing the letters itself) so that it becomes $$$b$$$. For example, the string "fortyfive" is an anagram of the string "overfifty", but the string "aabb" is not an anagram of the string "bbba".

Consider a path from the root of the tree to a leaf. The characters on the edges on this path form a string, we say that this string is associated with this leaf. The tree is anagrammable if and only if it is possible to replace each question mark with a lowercase English letter so that for all pair of leaves the associated strings for these leaves are anagrams of each other.

If the tree is anagrammable, then its anagramnity for the letter $$$c$$$ is the maximum possible number of letters $$$c$$$ in a string associated with some leaf in a valid replacement of all question marks.

Please after each update find if the tree is anagrammable and if yes, find the $$$\sum{f(c) \cdot ind(c)}$$$ for all letters $$$c$$$, where $$$f(c)$$$ is the anagramnity for the letter $$$c$$$, and $$$ind(x)$$$ is the index of this letter in the alphabet ($$$ind($$$"a"$$$) = 1$$$, $$$ind($$$"b"$$$) = 2$$$, ..., $$$ind($$$"z"$$$) = 26$$$).

Input format:
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 150\,000$$$, $$$1 \leq q \leq 150\,000$$$) — the number of vertices in the tree and the number of queries.

The next $$$n-1$$$ lines describe the initial tree. The $$$i$$$-th of them contains an integer $$$p_i$$$ and a character $$$c_i$$$ ($$$1 \leq p_i \leq i$$$, $$$c_i$$$ is a lowercase English letter or the question mark '?') describing an edge between vertices $$$p_i$$$ and $$$i+1$$$ with character $$$c_i$$$ written on it.

The root of this tree is the vertex $$$1$$$, and each vertex has at most two children.

The next $$$q$$$ lines describe the queries. The $$$i$$$-th of them contains two integers $$$v$$$ and $$$c$$$ ($$$2 \leq v \leq n$$$, $$$c$$$ is a lowercase English letter or the question mark '?'), meaning that updated character on the edge between $$$p_{v-1}$$$ to $$$v$$$ is $$$c$$$. The updated character can be the same as was written before.

Output format:
Output $$$q$$$ lines. In the $$$i$$$-th of them print "Fou" if the tree is not anagrammable after the first $$$i$$$ updates.

Otherwise output "Shi" and the $$$\sum{f(c) \cdot ind(c)}$$$ for all letters $$$c$$$.

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

Note:
In the first example after the first query, for each character, you can set all edges equal to that character, and you will get $$$1$$$ such character on each path, so the answer is $$$1 \cdot (1+2+\ldots+26) = 351$$$.

In the first example after the second query, you know that all paths should be an anagram of "a", so all paths should be "a", so the answer is $$$1 \cdot 1 = 1$$$.

In the first example after the third query, you have two paths with strings "a" and "b", but these strings are not anagrams, so the answer is "Fou".

In the first example after the fourth query, you know that all paths should be "b", so the answer is $$$1 \cdot 2 = 2$$$.

In the second example after the first query, you know that $$$f($$$'a'$$$) = 2$$$ and $$$f(c) = 1$$$ for all other characters, so the answer is $$$1 \cdot (2 + 3 + \ldots + 26) + 2 = 352$$$.

In the second example after the second query, you know that each path should contain one 'a' and one 'b', so the answer is $$$1 \cdot 1 + 1 \cdot 2 = 3$$$.

Example input:
3 4
1 ?
1 ?
2 ?
2 a
3 b
2 b

Example output:
Shi 351
Shi 1
Fou
Shi 2

Example input:
5 2
1 ?
1 ?
2 ?
3 ?
4 a
5 b

Example output:
Shi 352
Shi 3

Editorial:
Ok, let's make some useless (ha-ha, in fact not) observation at first, obviously, all leaves must have the same depth.
Now, I will define the criterion for the tree to be good.
Let $$$f(v,x)$$$ be the largest number of characters $$$x$$$ that contained on edges of some path from vertex $$$v$$$ to the leaf, and $$$len_v$$$ be the length of a path from $$$v$$$ to the leaf.
Lemma: tree is good iff for each vertex $$$\sum{f(v,x)} \leq len_v$$$.
Obviously, if the tree is good $$$\sum{f(v,x)} \leq len_v$$$ for each vertex because else you just don't have enough "space" in the subtree of the vertex to contain all required characters.
Why is it criterion? If for each vertex it is satisfied, from the root you can find some suitable characters on the edges from it, and then it is easy to see that you can restore the children by induction.
Ok, with this knowledge how to solve the problem? Maybe some spooky tree data structures will help us?...
Yup, you can do it with the "Dynamic tree DP technique" with HLD, and you will get the solution in $$$O(n \log^2 n)$$$ even for not a binary tree.
But it is not very easy to realize it :)
Let's remember that all leaves must have the same depth, so I will give you another Lemma!
Lemma: if you will "compress" all vertices with one son in the tree, where all leaves have an equal depth, then the depth of this tree will be $$$O(\sqrt{n})$$$.
Why? let $$$a_i$$$ be the number of vertices on the depth $$$i$$$, then $$$a_i \geq a_{i-1}$$$ for each $$$i \leq h$$$ as each vertex at the depth $$$i-1$$$ should have at least one son, and you have $$$\sum{a_i}=n$$$, so there are $$$O( \sqrt{n})$$$ distinct values among them, so almost all (without some $$$O(\sqrt{n})$$$ values) $$$i$$$ has $$$a_i = a_{i-1}$$$ (which means that all vertices at the depth $$$i-1$$$ has exactly one son).
So with this knowledge, you can "compress" the tree as I described, and after each query just go up from the end of the changed edge and recalculate the DP. Of course, each edge now will have several characters on it, so you should maintain a counter in each edge, but it is more a realization aspect.
Finally, here is the solution