Alice Learns Eertree!
Description
Just kidding! This problem isn't actually about eertree's.
Alice was eating a bowl of alphabet soup when she was magically transported to Wonderland! There she met the Mad Hatter who had a most devious plan in mind. While Alice was busy recovering from the existential crisis of being teleported to a new realm, the Hatter stole all $N$ of the letter-shaped noodles from Alice's alphabet soup and gave them to the Cheshire Cat.
Curiously, the Cheshire Cat lives in a tree consisting of $N$ nodes and $N - 1$ branches such that the set of nodes is connected when the branches are though of as undirected edges, and there exists a unique shortest path between any pair of nodes (hence the tree is in fact a tree). The evil Cheshire Cat takes each of the noodle letters and places them in a different node of the tree such that each node has exactly one letter associated with it (if there are duplicate letters, multiple nodes may be assigned the same letter, but no node will be left without a letter).
The Mad Hatter now gives Alice a contrived puzzle, stating that she can only win her soup back if she solves it! Specifically, the Hatter wants Alice to figure out for each node $u$, if the tree was rooted at $u$, how many non-empty subtrees of the tree would be able to have their associated letters rearranged into a palindrome?
Note that a subtree in a rooted tree is a node along with all of its descendants. A palindrome is a word which is the same forwards and backwards. More formally, a string $s = s_1s_2\dots s_l$ is a palindrome if $s_i = s_{l-i+1}$ for all $i \in \{1, 2, \dots, l\}$.
Given the structure of the Cheshire Cat's tree and the arrangement of the letter-shaped noodles across the nodes, can you help Alice figure out the Hatter's riddle and help her get her noodle soup back?
The input will begin with a line containing a single positive integer $N\ (1 \leq N \leq 2 \cdot 10^5)$, denoting both the number of noodle letters in Alice's noodle soup as well as the number of nodes in the Cheshire Cat's tree.
The next line will contain a string of $N$ uppercase English letters $s_1s_2\dots s_N$. The $i$th letter, $s_i$, will be placed in the $i$th node of the Cheshire Cat's tree.
The final $N - 1$ lines of input will each contain two space-separated integers $u,\ v\ (1 \leq u, v \leq N,\ u \neq v)$ denoting a branch (edge) between the $u$th and $v$th nodes in the tree. It is guaranteed that these edges will form a tree.
The output should consist of $N$ lines, each containing a single nonnegative integer. In particular, the $i$th line of output should contain the number of non-empty subtrees of the tree which would be able to have their associated letters rearranged into a palindrome if the tree was rooted at the $i$th node.
Input
The input will begin with a line containing a single positive integer $N\ (1 \leq N \leq 2 \cdot 10^5)$, denoting both the number of noodle letters in Alice's noodle soup as well as the number of nodes in the Cheshire Cat's tree.
The next line will contain a string of $N$ uppercase English letters $s_1s_2\dots s_N$. The $i$th letter, $s_i$, will be placed in the $i$th node of the Cheshire Cat's tree.
The final $N - 1$ lines of input will each contain two space-separated integers $u,\ v\ (1 \leq u, v \leq N,\ u \neq v)$ denoting a branch (edge) between the $u$th and $v$th nodes in the tree. It is guaranteed that these edges will form a tree.
Output
The output should consist of $N$ lines, each containing a single nonnegative integer. In particular, the $i$th line of output should contain the number of non-empty subtrees of the tree which would be able to have their associated letters rearranged into a palindrome if the tree was rooted at the $i$th node.
4
HELP
1 2
2 4
3 4
5
AAAAA
1 2
2 3
3 4
4 5
1
2
1
2
5
5
5
5
5
Note
In the first sample, the tree looks something like this:
In this case, regardless of the rooting of the tree, the only subtrees which can have their letters rearranged into palindromes are the leaves of the tree.
In the second sample, the tree looks something like this:
In this case, every letter is the same, so every subtree can have its letters rearranged into palindromes regardless of the rooting of the tree.
In both cases, the nodes are labeled with the letter they are assigned as well as their node number to avoid ambiguity.