## 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 perform 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 ab 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```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e4+5;
const int LG = log2(MAXN) + 1;

int n;
int level[MAXN], par[MAXN][LG], cost[MAXN];

void dfs(int u, int parent, int c){
cost[u] = cost[parent] + c;
level[u] = level[parent] + 1;
par[u][0] = parent;
if(v.first == parent)	continue;
dfs(v.first, u, v.second);
}
}

int lca(int u, int v){
if(level[u] < level[v])	swap(u, v);
int log = log2(level[u]);
for(int i = log; i >= 0; i--)
if(level[u]-level[v] >= (1 << i))
u = par[u][i];
if(u == v)
return u;
for(int i = log; i >= 0; i--){
if(par[u][i] != -1 && par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
return par[u][0];
}

int kth(int n, int k){
int log = log2(level[n]);
for(int i = 0; i <= log; i++){
if(k & (1 << i))
n = par[n][i];
}
return n;
}

int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 1;i <= n; i++){
level[i] = 0;
}
for(int i = 0;i < n-1; i++){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
}
memset(par, -1, sizeof par);
level[0] = -1;
dfs(1, 0, 0);
for(int j = 1; j < LG; j++){
for(int i = 1; i <= n; i++){
if(par[i][j-1] != -1)
par[i][j] = par[par[i][j-1]][j-1];
}
}
char query[8];
while(scanf("%s", query) == 1){
if(query[1] == 'O')	break;
int a, b;
scanf("%d%d", &a, &b);
if(query[1] == 'I'){
int lc = lca(a, b);
int ans = cost[a] + cost[b] - 2*cost[lc];
printf("%d\n", ans);
}else{
int k;
scanf("%d", &k);
int lc = lca(a, b);
int left = level[a]-level[lc]+1;
if(k <= left)
printf("%d\n", kth(a, k-1));
else
printf("%d\n", kth(b, (level[b]-level[lc])-(k-left)));
}
}
printf("\n");
}
return 0;
}``````
Copy The Code &

Input

cmd
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

cmd
5
3