树上跳跃（Jump on Tree）

问题描述

给定一棵含 $N$ 个顶点的树，其中第 $i$ 条边（$0 \le i < N-1$）连接顶点 $a_i$ 和 $b_i$。
请按顺序处理以下 $Q$ 个查询：

• s t i：设从 $s$ 到 $t$ 的最短路径为 $(v_0, v_1, \dots, v_k)$，其中 $v_0 = s$、$v_k = t$。若 $i \le k$，输出 $v_i$；否则输出 -1。

约束条件

• $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 \ne b_i$
• $0 \leq s, t \leq N-1$
• $0 \leq i \leq N-1$

输入格式

$N\ Q$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{N-2}\ b_{N-2}$
$s_0\ t_0\ i_0$
$s_1\ t_1\ i_1$
:
$s_{Q-1}\ t_{Q-1}\ i_{Q-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

5
-1
4
1
2
3
-1
6
2
1
4
7
-1