P8994 [Peking University Training 2021] Classic Game

CTT2021 D4T2.

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**.

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$.

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.

| Subtask Score | $1\le n,m\le$ | $\max\{a_1,a_2,\dots,a_n\}\le$ | Special Property | | :-----------: | :-----------: | :----------------------------: | :--------------: | | $16$ | $5$ | $1$ | None | | $15$ | $300$ | $1$ | None | | $14$ | $5000$ | $10^9$ | None | | $13$ | $100000$ | $10^9$ | Guaranteed that the given tree is a chain. | | $12$ | $100000$ | $10^9$ | Guaranteed that the tree has a node with degree $n-1$. | | $11$ | $100000$ | $10^9$ | Guaranteed that the initially given root is the same across the $m$ games. | | $10$ | $500000$ | $10^9$ | None | | $9$ | $1000000$ | $10^9$ | None | Translated by ChatGPT 5