Disk Storage — palindromePaths on Rooted Tree

The tree is rooted at 0. For each query node q, count the ancestors v of q (including q itself) such that the letters of all the nodes on the path from q to v can be rearranged into a palindrome. A palindromic rearrangement exists exactly when at most one letter occurs an odd number of times.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n m, the second line contains a string of n lowercase letters, followed by n−1 lines of undirected edges u v, and the last line contains m query nodes. 1≤n,m≤100000, nodes are numbered 0..n−1, and the tree is guaranteed to be valid.

输出格式

Output one integer answer.

样例 1

输入：

7 3
abcacbc
0 1
1 2
2 3
2 4
4 5
4 6
6 5 3

输出：

3 4 1

样例 2

输入：

3 2
aaa
0 1
1 2
2 0

输出：

3 1

样例 3

输入：

2 1
ab
0 1
1

输出：

1

样例说明

Example 1: checking every ancestor path according to the statement gives 3 4 1. Example 2: every path of identical letters can be rearranged into a palindrome; node 2 has 3 ancestors and the root has 1, so the output is 3 1. Example 3: node 1 itself, b, is valid, but ba cannot be rearranged into a palindrome, so the output is 1.