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