102675: [AtCoder]ABC267 F - Exactly K Steps

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

问题描述

给你一棵有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。

约束

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)$
• 给定的图是一棵树。
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)$
• 输入中的所有值都是整数。

输入

输入从标准输入给出，格式如下：

$N$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$Q$
$U_1$ $K_1$
$\vdots$
$U_Q$ $K_Q$

输出

输出$Q$行。第$i$行（$1 \leq i \leq Q$）应包含与顶点$U_i$距离恰好为$K_i$的顶点的索引，如果存在这样的顶点；否则，应包含 -1。如果存在多个这样的顶点，你可以输出其中任何一个。

样例输入1

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

样例输出1

4
1
-1

• 有两个顶点，顶点$4$和$5$与顶点$2$的距离恰好为$2$。
• 只有一个顶点，顶点$1$与顶点$5$的距离恰好为$3$。
• 没有顶点与顶点$3$的距离恰好为$3$。

样例输入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

样例输出2

2
4
10
-1
-1