P16338 「ALFR Round 10」Card game

There are $n$ players playing a certain card game, numbered from $1$ to $n$. The players form a tree structure. Player $i$ initially has $a_i$ cards and $b_i$ energy points. You are player $d$. At the beginning of the game, everyone agrees on an integer $u$. Then player $u$ chooses a permutation $p_1,\ldots,p_n$, such that $p$ is a [DFS order](https://oi-wiki.org/graph/dfs/#dfs-%E5%BA%8F%E5%88%97) of the original tree when rooted at $u$. Initially, let $k=0$. Then for each $i=1,2,\ldots,n$ in order, player $p_i$ must choose **exactly one** of the following actions: 1. Discard some cards from their hand. The number of discarded cards must be at most $a_{p_i}$, and must be at least the number discarded by the previous player who chose to discard, plus $1$. Formally, choose an integer $x$ such that $k < x \le a_{p_i}$, and set $k \gets x$. **In particular, if $\boldsymbol{k \ge a_{p_i}}$, then this action cannot be chosen.** 2. Lose $2$ energy points. Formally, set $b_{p_i} \gets b_{p_i} - 2$. Once a player's remaining energy becomes $\le 0$, they are eliminated. You win if and only if after the entire process ends, you are **not eliminated**, regardless of whether other players are eliminated. You want to know how many integers $u$ with $1 \le u \le n$ satisfy the following: There exists some strategy of the other players (excluding you), such that no matter what you do, you will inevitably lose.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, denoting the number of test cases. For each test case: The first line contains two positive integers $n,d$, representing the number of nodes in the tree and your player index. The next $n$ lines each contain two integers $a_i,b_i$. The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between nodes $u$ and $v$ in the tree.

For each test case, output one line containing one integer: the required answer.

### Explanation of Sample 1 When $u \in \{2,3,4,5\}$, there exists an optimal strategy for the opponents that guarantees your failure. For example, when $u=3$, one possible DFS order rooted at $3$ is $3,4,1,2,5$. Following this order: - Player $3$ chooses to lose $2$ energy points. - Player $4$ chooses to discard $a_4=2$ cards. Then you (player $1$) must discard at least $2+1=3$ cards, but $a_1=1$, so you cannot choose the discard action. You are forced to lose $2$ energy points and are eliminated immediately. Therefore, you lose. ### Explanation of Sample 2 Since $b_3>2$, no matter what strategy the opponents use, you can always choose to lose $2$ energy points without being eliminated. Therefore, you are guaranteed to win. ### Constraints **This problem uses bundled subtasks.** | Subtask ID | $n \le$ | Special Property | Score | | :--------: | :-----: | :--------------: | :---: | | $1$ | $10$ | $\text{A}$ | $10$ | | $2$ | $100$ | None | $15$ | | $3$ | $10^4$ | $\text{B}$ | $20$ | | $4$ | $10^4$ | $\text{C}$ | $25$ | | $5$ | $10^5$ | None | $30$ | Special property $\text{A}$: it is guaranteed that $T \le 5$. Special property $\text{B}$: the tree is generated as follows: after fixing $n$, for each $2 \le i \le n$, an integer $x$ is chosen uniformly at random from $[1,i)$, and an edge is added between $x$ and $i$. Special property $\text{C}$: it is guaranteed that $a_i \le 10$. For all test cases, it is guaranteed that $T \le 100$, $2 \le n \le 10^5$, $\sum n \le 10^6$, $1 \le a_i,b_i \le 10^9$, $1 \le d \le n$.