E. Clean White Paths
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a tree of $$$n$$$ vertices, each node is initially either black or white.

A path from node $$$u$$$ to node $$$v$$$ is:

  • white if both nodes $$$u$$$ and $$$v$$$ are white.
  • black if both nodes $$$u$$$ and $$$v$$$ are black.
  • otherwise it is a normal path neither white nor black.

A white path is clean if and only if there is no black path that contains this white path as a subpath of it.

A path is a subpath from another path if the set of vertices of this path forms a subset of the vertices of the other path.

The score of the tree is the number of Clean White Paths.

Note that path $$$(u,v)$$$ is the same as path $$$(v,u)$$$ and has to be counted once, and you have to count paths of the form $$$(u,u)$$$.

Given $$$q$$$ update queries, in each query you are given an integer $$$u$$$, make the node $$$u$$$ black.

After each query, print the score of the tree.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n \le 3 \times 10^5)$$$ $$$(1 \le q \le 3 \times 10^5)$$$ , the size of the tree and the number of queries respectively.

The second line of each test case contains a binary string $$$s$$$ of size $$$n$$$ $$$(s_i \in (0,1))$$$ , if $$$s_i$$$ is $$$1$$$ then the $$$i_{th}$$$ node is white, otherwise the node is black.

The next $$$n-1$$$ lines describe the edges of the tree, each line contains two integers $$$u$$$,$$$v$$$ $$$(1 \le u,v \le n)$$$, which means there is an edge between node $$$u$$$ and node $$$v$$$.

Each of the next $$$q$$$ lines contains a single integer $$$u$$$ $$$(1 \le u \le n)$$$, the node to make black.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$3 \times 10^5$$$.

Output

In each test case, after each query print the score of the tree.

Example
Input
1
5 5
11111
5 2
1 3
5 4
3 4
4
3
2
4
1
Output
10
6
2
2
0
Note

After the first update, node $$$4$$$ is black; all white paths are clean, so the answer is $$$10$$$.

After the third update, there are two clean white paths: $$$(1,5)$$$ and $$$(1,1)$$$.