## QTREE2 - Query on a tree II

You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.

We will ask you to perfrom some instructions of the following form:

• DIST a b : ask for the distance between node a and node b
or
• KTH a b k : ask for the k-th node on the path from node a to node b

Example:
N = 6
1 2 1 // edge connects node 1 and node 2 has cost 1
2 4 1
2 5 2
1 3 1
3 6 2

Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6
DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5)
KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)

### Input

The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.

For each test case:

• In the first line there is an integer N (N <= 10000)
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of cost c (c <= 100000)
• The next lines contain instructions "DIST a b" or "KTH a b k"
• The end of each test case is signified by the string "DONE".

There is one blank line between successive tests.

### Output

For each "DIST" or "KTH" operation, write one integer representing its result.

Print one blank line after each test.

### Example

```Input:
1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

Output:
5
3
```

hide comments
 < Previous 1 2 3 4 Next > zengshiyuan: 2014-10-02 10:48:37 Easy problem.Can use heavy-light decomposition to get lca. Chandan Mittal: 2014-07-18 20:25:02 can there be a case when k is greater than number of nodes between a and b, both inclusive? Mojtaba FayazBakhsh: 2013-08-21 17:05:54 got AC using 32 bit integer Parit Agarwal: 2013-07-16 07:52:46 getting SIGSEGV .... Donot know why.. my submission id is 9660500 plz help Last edit: 2013-07-16 07:53:30

 Added by: Thanh-Vy Hua Date: 2006-08-27 Time limit: 0.433s Source limit: 15000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Special thanks to Ivan Krasilnikov for his alternative solution