3670 . [模板題] Jump on Tree
TopCoder
Tags
Description
Given a tree with $N$ vertices, where the $i$-th edge connects vertex $a_ i$ and $b_ i$. Process $Q$ queries as follows:
s t i: Print $v_ i$, where the shortest path on the tree from $s$ to $t$ is $(v_ 0, v_ 1, \ldots, v_ k)$ ($v_ 0 = s$, $v_ k = t$). If $i>k$, print-1.
Input Format
$N$ $Q$
$a_ 0$ $b_ 0$
$\vdots$
$a_ {N-2}$ $b_ {N-2}$
$s_ 0$ $t_ 0$ $i_ 0$
$\vdots$
$s_ {Q-1}$ $t_ {Q-1}$ $i_ {Q-1}$
Output Format
Sample Input 1
8 13 0 1 1 2 2 3 1 4 4 7 1 5 2 6 5 5 0 5 5 1 4 3 0 4 3 1 4 3 2 4 3 3 4 3 4 6 7 0 6 7 1 6 7 2 6 7 3 6 7 4 6 7 5
Sample Output 1
5 -1 4 1 2 3 -1 6 2 1 4 7 -1
Hints
- $2 \leq N \leq 5 \times 10^ {5}$
- $1 \leq Q \leq 5 \times 10^ {5}$
- $0 \leq a_ i, b_ i \leq N-1$
- $a_ i \neq b_ i$
- $0 \leq s, t \leq N - 1$
- $0 \leq i \leq N - 1$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|