1687 . 樹上詢問 Query on a Tree II
TopCoder
Tags
Description
你得到了一棵N個節點的樹!!(頂點編號1~N)
你選定了一個起點S跟一個終點T，
現在你從S走到T，請求出走第K步時走到的點。
(K=0表示還待在S)。
Input Format
每個檔案只有一筆測資。
第一行有兩個數字N、Q，其中N <= 100,000、Q <= 200,000
表示這棵樹有N個節點、有Q筆詢問
接下來的N-1行，每行有兩數字A,B，表示A和B之間有一條邊。
再來有Q行，每行有三個數字S,T,K，表示詢問S往T走K步走到的點。
保證A,B,S,T都是1~N的正整數。
Output Format
輸出包含Q行，每行僅含一個數字，代表S往T走K步走到的點。
若K > S到T的步數，輸出-1。
Sample Input 1
6 7
1 2
2 4
2 5
1 3
3 6
4 6 0
4 6 1
4 6 2
4 6 3
4 6 4
4 6 5
4 6 6
1 2
2 4
2 5
1 3
3 6
4 6 0
4 6 1
4 6 2
4 6 3
4 6 4
4 6 5
4 6 6
Sample Output 1
4
2
1
3
6
-1
-1
2
1
3
6
-1
-1
Hints
Problem Source
原TIOJ1687 / SPOJ Query on a tree II 修改&簡化
Problem setter: worm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |