← 返回题目列表

AtCoder · abc267_f

I. 正好 K 步骤

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你得到了一棵树 N 顶点。 顶点已编号 1, \dots, N,以及 i-th (1 \leq i \leq N - 1) 边连接顶点 A_i 和 B_i.

我们定义 距离 顶点之间 u 和 v 在这棵树上通过从顶点开始的最短路径中的边数 u 到顶点 v.

你被给予 Q 查询。 在 i-th (1 \leq i \leq Q) 查询,给定整数 U_i 和 K_i,打印距 Vertex 距离的任何顶点的索引 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-th (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 的距离正好 3 来自顶点 5.
  • 没有顶点具有精确的距离 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