P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

Given an unrooted tree with $n$ nodes, the distance between adjacent nodes is $1$. At the beginning, you are at node $m$. Then you will receive $k$ commands one by one. Each command contains two integers $d$ and $t$. You need to move toward node $d$ along the shortest path within $t$ steps (including exactly $t$ steps). If you cannot reach $d$ within $t$ steps, then you stop at the last node you can reach. After each command, output your current position.

The first line contains three integers $n, m, k$. The next $n - 1$ lines each contain two integers $x, y$, representing an edge of the tree. The next $k$ lines each contain two integers $d, t$, representing a command.

One line containing $k$ integers, where the $i$-th integer is the node you are at after executing the $i$-th command.

For $100\%$ of the data, $1 \leq m \leq n \leq 10^6$, $1 \leq k \leq 10^6$, $1 \leq x, y, d \leq n$, $0 \leq t \leq 10^9$. Translated by ChatGPT 5