Description:

Solution:

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f;

	char c = getchar();

	while(!isdigit(c) && c != '-')c = getchar();

	if(c == '-'){f = -1;c = getchar();}

	else f = 1;

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

inline char getc()

{

	char c,p = getchar();

	while('A' <= p && p <= 'Z'){c = p;p = getchar();}

	return c;

}

int testcases;

int n;

#define MAXN 10010

struct node

{

	int fa,c[2],v,sumv,siz;

	bool rev;

	node(){fa = c[0] = c[1] = v = sumv = siz = 0;rev = false;}

}t[MAXN << 1];

inline void maintain(int rt)

{

	t[rt].siz = t[t[rt].c[0]].siz + t[t[rt].c[1]].siz + 1;

	t[rt].sumv = t[rt].v;

	if(t[rt].c[0])t[rt].sumv += t[t[rt].c[0]].sumv;

	if(t[rt].c[1])t[rt].sumv += t[t[rt].c[1]].sumv;

	return;

}

inline bool isroot(int x){return (t[t[x].fa].c[0] != x && t[t[x].fa].c[1] != x);}

inline int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

inline void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

inline void rotate(int x)

{

	register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	maintain(y);maintain(x);

	return;

}

inline void pushdown(int rt)

{

	if(!t[rt].rev)return;

	t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

	swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	return;

}

stack<int> s;

inline void splay(int x)

{

	s.push(x);

	for(register int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		register int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

inline void access(int k){for(register int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

inline void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

inline void link(int x,int y){makeroot(x);t[x].fa = y;return;}

inline void work()

{

	scanf("%d",&n);

	memset(t,0,sizeof(t));

	for(register int i = 1;i < n + n;++i)

	{

		t[i].siz = 1;

	}

	int a,b,c;

	for(register int i = 1;i < n;++i)

	{

		a = read();b = read();c = read();

		link(a,i + n);

		link(b,i + n);

		splay(i + n);

		t[i + n].v = c;

		maintain(i + n);

	}

	char ch;

	while(true)

	{

		ch = getc();

		if(ch == 'E')break;

		if(ch == 'H')

		{

			a = read();b = read();c = read();c = c * 2 - 1;

			makeroot(a);access(b);splay(b);

			int cur = b;

			while(true)

			{

				pushdown(cur);

				if(c <= t[t[cur].c[0]].siz)cur = t[cur].c[0];

				else if(c > t[t[cur].c[0]].siz + 1){c -= t[t[cur].c[0]].siz + 1;cur = t[cur].c[1];}

				else break;

			}

			printf("%d\n",cur);

		}

		if(ch == 'T')

		{

			a = read();b = read();

			makeroot(a);access(b);splay(b);

			printf("%d\n",t[b].sumv);

		}

	}

	puts("");

	return;

}

int main()

{

	scanf("%d",&testcases);

	for(register int i = 1;i <= testcases;++i)work();

	return 0;

}