TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

91.4% (32/35)

Submission's AC Ratio

37.3% (50/134)

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

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6