No.2726 Rooted Tree Nim
MasKoaTS
nok0
ygussanyProblem Statement
You are given an undirected rooted tree consisting of $N$ vertices numbered $1, 2, \dots, N$. Vertex $1$ is the root.
The $i$-th $(1 \leq i \leq N - 1)$ edge of the rooted tree connects vertex $X_{i}$ and vertex $Y_{i}$.
Initially, $A_{i}$ stones are placed on vertex $i$ $(1 \leq i \leq N)$.
Now, Koa and Pache will play a game. Starting with Koa, they alternately perform the following operation.
First, from the vertices of the rooted tree excluding vertex $1$, which are $N-1$ in number, consider those with $1$ or more stones placed on them, choose $1$ of them, and call it $v$.
Next, remove at least $1$ and at most $K$ stones from $v$, and place all of them on the parent vertex of $v$.
The player who first becomes unable to perform the operation loses.
Determine who wins when both players play optimally.
$T$ test cases are given; find the answer for each of them.
Constraints
$1 \leq T \leq 10^{5}$
$2 \leq N \leq 2 \times 10^{5}$
$1 \leq X_{i}, Y_{i} \leq N$ $(1 \leq i \leq N - 1)$
$1 \leq K \leq 10^{9}$
$1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
The sum of $N$ given in $1$ input is at most $2 \times 10^{5}$
Every graph given in the input is an undirected rooted tree with vertex $1$ as the root
All input values are integers
Input
The input is given in the following format.
$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$
Each test case is given in the following format.
$N$ $K$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
$\vdots$
$X_{N-1}$ $Y_{N-1}$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
Output
Print the answers, $1$ per line, for a total of $T$ lines.
On the $i$-th $(1 \leq i \leq T)$ line, when the game is played on the $i$-th test case, if Koa wins, print K, and if Pache wins, print P.
Sample
Sample 1
Input
4 4 2 1 2 1 3 2 4 1 3 4 2 6 10 3 1 2 3 5 4 3 6 5 1 999 100 375 109 210 712 2 1 1 2 2 1 8 6 2 4 2 8 7 2 1 2 2 3 5 2 6 2 3 14 15 92 6 53 5 89
Output
K P K P
In the $1$-st test case, Koa has a winning strategy. For example, the operations proceed as follows.
Koa removes, from vertex $3$, $1$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $2, 3, 3, 2$, respectively.Pache removes, from vertex $2$, $2$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $4, 1, 3, 2$, respectively.Koa removes, from vertex $4$, $2$ of the stones placed there, and places all of them on vertex $2$.
At this point, the numbers of stones on the vertices are $4, 3, 3, 0$, respectively.Pache removes, from vertex $2$, $2$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $6, 1, 3, 0$, respectively.Koa removes, from vertex $3$, $2$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $8, 1, 1, 0$, respectively.Pache removes, from vertex $3$, $1$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $9, 1, 0, 0$, respectively.Koa removes, from vertex $2$, $1$ of the stones placed there, and places all of them on vertex $1$.
At this point, the numbers of stones on the vertices are $10, 0, 0, 0$, respectively.There is no vertex that Pache can choose, so Koa wins.
Finding the answers for the remaining test cases in the same way gives the sample output above.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。