Background

CTT2021 D4T2.

Problem Description

One day, C and K felt bored, so they decided to play a classic mini-game.

On a rooted tree with $n$ nodes, node $i$ has $a_i$ tokens. Players take turns to make moves. In each move, a player may take one token from any node $u$ and place it onto any node $v \in U(u)$, where $U(u)=subtree\{u\}\setminus\{u\}$, meaning the set of nodes in the subtree of $u$ (excluding $u$ itself). The player who cannot make a move loses.

However, since C and K are students of P** and T**, this kind of game where you can see the winning strategy at a glance is too boring. So they thought it would be more fun if each of them had a special ability.

Before the game starts, C may choose to change the current root $R$ of the tree to any node $R^{\prime}$ adjacent to $R$. Two nodes are adjacent if and only if there is an edge directly connecting them.

Before the game starts, K must choose one node in the tree and add one token on it.

C and K will play $m$ games. The process of each game is as follows:

1. Before the game starts, C and K agree to first place one token on the node with label $x$, and then set the root of the tree to $y$.
2. Then C may choose whether to use the special ability. After C finishes the decision, K may choose whether to use the special ability.
3. After the decisions about special abilities are finished, they play one game on this tree with C moving first and K moving second. After the game ends, the token configuration on the tree is restored to the state right after step 1 ends.

C thinks this game can be made into an easy problem, so he decides to test you: in step 2 of each game, how many decision choices does C have such that no matter how K uses the special ability, C has a winning strategy at the start of the game? Two decision choices are considered different if and only if the new root $R^{\prime}$ chosen by the two decisions is different, or exactly one of them does not use the special ability.

Input Format

The first line contains one integer, representing the score of the subtask for this test point. You may use this information to determine the special properties satisfied by this test point. In particular, in the samples provided, this line is replaced by $0$.

The second line contains two positive integers $n, m$ separated by spaces, denoting the number of nodes in the tree and the number of games. The nodes are numbered from $1$ to $n$.

The next $n-1$ lines each contain two positive integers $u_i, v_i$ separated by spaces, satisfying $1 \le u_i,v_i \le n$, indicating that there is an edge directly connecting nodes $u_i$ and $v_i$.

The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ separated by spaces, satisfying $0 \leq a_1,a_2,\ldots,a_n \leq 10^9$.

The next $m$ lines each contain two positive integers $x, y$ separated by spaces, describing one game, satisfying $1 \le x,y \le n$.

Output Format

You need to output $m$ lines. The $i$-th line should contain a non-negative integer $x$ indicating, in the $i$-th game, how many decision plans C has for using the special ability such that C has a winning strategy in this game. Note that not using the special ability is also a possibly feasible decision plan.

0
5 2
1 2
1 3
2 4
2 5
1 0 1 0 1
2 2
4 4

2
1

0
10 10
6 3
7 4
8 2
2 1
9 1
1 3
3 4
4 5
5 10
0 0 1 1 1 0 1 1 0 0 
8 3
2 3
7 10
7 3
6 7
8 5
9 8
2 10
5 4
3 9

1
1
0
1
1
1
0
0
2
1

Hint

Translated by ChatGPT 5