F - Exactly K Steps Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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
  • 頂点 2 からの距離がちょうど 2 であるのは頂点 4, 5 の二つです。
  • 頂点 5 からの距離がちょうど 3 であるのは頂点 1 のみです。
  • 頂点 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

Score : 500 points

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