Score : $500$ points

问题描述

给定一棵包含 $N$ 个顶点的树。顶点编号为 $1, \dots, N$，第 $i$ 个（$1 \leq i \leq N - 1$）边连接顶点 $A_i$ 和 $B_i$。

我们定义此树中顶点 $u$ 和顶点 $v$ 之间的 距离 为从顶点 $u$ 到顶点 $v$ 的最短路径上的边数。

你将得到 $Q$ 个查询。在第 $i$ 个查询（$1 \leq i \leq Q$）中，给定整数 $U_i$ 和 $K_i$，输出距离顶点 $U_i$ 正好为 $K_i$ 的任意一个顶点的索引。如果没有这样的顶点，则输出 -1。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered $1, \dots, N$, and the $i$-th ($1 \leq i \leq N - 1$) edge connects Vertices $A_i$ and $B_i$.

We define the distance between Vertices $u$ and $v$ on this tree by the number of edges in the shortest path from Vertex $u$ to Vertex $v$.

You are given $Q$ queries. In the $i$-th ($1 \leq i \leq Q$) query, given integers $U_i$ and $K_i$, print the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$. If there is no such vertex, print -1.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)$
• The given graph is a tree.
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$

$A_1$ $B_1$

$\vdots$

$A_{N-1}$ $B_{N-1}$

$Q$

$U_1$ $K_1$

$\vdots$

$U_Q$ $K_Q$

Output

Print $Q$ lines. The $i$-th ($1 \leq i \leq Q$) line should contain the index of any vertex whose distance from Vertex $U_i$ is exactly $K_i$ if such a vertex exists; if not, it should contain -1. If there are multiple such vertices, you may print any of them.

Sample Input 1

5
1 2
2 3
3 4
3 5
3
2 2
5 3
3 3

Sample Output 1

4
1
-1

• Two vertices, Vertices $4$ and $5$, have a distance exactly $2$ from Vertex $2$.
• Only Vertex $1$ has a distance exactly $3$ from Vertex $5$.
• No vertex has a distance exactly $3$ from Vertex $3$.

Sample Input 2

10
1 2
2 3
3 5
2 8
3 4
4 6
4 9
5 7
9 10
5
1 1
2 2
3 3
4 4
5 5

Sample Output 2

2
4
10
-1
-1

update @ 2024/3/10 11:17:06