TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

41.9% (44/105)

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

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

Sample Output

4
2
1
3
6
-1
-1

Hints

Problem Source

原TIOJ1687 / SPOJ Query on a tree II 修改&簡化
Problem setter: worm

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144