这个做法。。。纯粹。。。。恶心自己。。。。泪奔。。。。

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# include <vector>
using namespace std;
const int SIZE = 10007;
const int INF = 2147483647;
int t, n;
struct EDGE { int v, next, len; } e[SIZE<<1];
int h[SIZE], tot, Edgesign[SIZE];
void AddEdge(int u, int v, int len)
{
	e[++tot].v = v;
	e[tot].len = len;
	e[tot].next = h[u];
	h[u] = tot;
}
bool vis[SIZE];
int tree[(SIZE<<1)<<2], pos[(SIZE<<1)<<2], M;
int list[SIZE<<1], firstshow[SIZE], ltot;
int tsize[SIZE], Ednode[SIZE], dist[SIZE];
int Generfa(int s, int t)
{
	s = firstshow[s];
	t = firstshow[t];
	if ( s > t ) swap(s, t);
	int ans = 0, min = INF;
	for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1)
	{
		if (~s&1 && tree[s^1] < min) min = tree[s^1], ans = pos[s^1];
		if ( t&1 && tree[t^1] < min) min = tree[t^1], ans = pos[t^1];
	}
	return list[ans];
}
inline void Intree(int &x, int &d)
{
	tree[M + (++ltot)] = d;
	list[ltot] = x;
	pos[M+ltot] = ltot;
	if ( firstshow[x] == 0 ) firstshow[x] = ltot;
}
void LCA(int x, int d)
{
	vis[x] = true;
	Intree(x, d);
	tsize[x] = 1;
	dist[x] = d;
	for (int i = h[x]; i; i = e[i].next)
	{
		if ( vis[e[i].v] ) continue;
		LCA(e[i].v, d+1);
		Intree(x, d);
		tsize[x] += tsize[e[i].v];
		Ednode[e[i].v] = e[i].len; //边权加在点上
	}
	vis[x] = false;
}
class Sgttree
{
	public:
	vector <int> tree;
	int size, M;
	void Init(int insize)
	{
		size = insize; tree.clear();
		if ( size == 1 ) tree.resize(7);
		else tree.resize(size<<2);
		for (M = 1; M <= size + 1; M <<= 1);
		for (int i = (size<<2) - 1; i; --i ) tree[i] = -INF;
	}
	void Build()
	{
		for (int i = M - 1; i; --i )
			if ( tree[i<<1] > tree[(i<<1)+1] ) tree[i] = tree[i<<1];
			else tree[i] = tree[(i<<1)+1];
	}
	void Modify(int x, int n)
	{
		tree[n+=M] = x;
		for ( n >>= 1; n; n >>= 1 ) tree[n] = max(tree[n<<1], tree[(n<<1)+1]);
	}
	int getmax(int s, int t)
	{
		int max = -INF;
		if ( s > t ) swap(s, t);
		for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
		{
			if (~s&1 && tree[s^1] > max ) max = tree[s^1];
			if ( t&1 && tree[t^1] > max ) max = tree[t^1];
		}
		return max;
	}
}_st;
vector <Sgttree> sgtree;
int belong[SIZE], sgttot, sgtsize[SIZE], sgtpos[SIZE], pointpos[SIZE];
int firptr[SIZE]; //当前线段树中第一个节点编号
int fa[SIZE];
void SelcEdge(int x)
{
	vis[x] = true;
	int i, maxsize = -INF, which;
	for (i = h[x]; i; i = e[i].next)
		if ( !vis[e[i].v] && tsize[e[i].v] > maxsize ) maxsize = tsize[e[i].v], which = e[i].v;
	for (i = h[x]; i; i = e[i].next)
	{
		if ( vis[e[i].v] ) continue;
		if ( e[i].v == which )
		{
			if( belong[x] == -1 ) belong[e[i].v] = ++sgttot;
			else belong[e[i].v] = belong[x];
		}
		else belong[e[i].v] = -1; //标记为轻边指向点
		SelcEdge(e[i].v);
	}
	vis[x] = false;
}
inline void InsertSgt(int x)
{
	int k = belong[x];
	if ( sgtpos[k] == 0 ) firptr[k] = x;
	sgtree[k].tree[sgtree[k].M + (++sgtpos[k])] = Ednode[x];
	pointpos[x] = sgtpos[k];
}
void CreatSgt(int x)
{
	vis[x] = true;
	if ( belong[x] != -1 ) InsertSgt(x);
	for (int i = h[x]; i; i = e[i].next )
	{
		if ( vis[e[i].v] ) continue;
		CreatSgt(e[i].v);
		fa[e[i].v] = x;
	}
	vis[x] = false;
}

void Init()
{
	int i, a, b, c;
	scanf("%d", &n);
	memset(h, 0, sizeof(h));
	memset(vis, 0, sizeof(vis));
	memset(firstshow, 0, sizeof(firstshow));
	memset(tree, 44, sizeof(tree));
	memset(sgtsize, 0, sizeof(sgtsize));
	memset(sgtpos, 0, sizeof(sgtpos));
	sgtree.clear();
	tot = ltot = sgttot = 0;
	Ednode[1] = -INF;
	for ( M = 1; M <= (n<<1)+1; M <<= 1 );
	for (i = 1; i != n; ++i )
	{
		scanf("%d%d%d", &a, &b, &c);
		AddEdge(a,b,c); Edgesign[i] = tot;
		AddEdge(b,a,c);
	}
	LCA(1,0);
	for (i = ltot+M; i; --i )
		if ( tree[i>>1] > tree[i] ) tree[i>>1] = tree[i], pos[i>>1] = pos[i];

}
void change(int x, int a)
{
	int b = e[ Edgesign[a]+1].v, k;
	a = e[ Edgesign[a] ].v;
	if( dist[a] < dist[b] ) a = b;
	k = belong[a];
	if ( k != -1 ) sgtree[k].Modify(x, pointpos[a]);
	else Ednode[a] = x;
}
int find(int a, int b)
{
	if ( a == b ) return 0;
	int root = Generfa(a, b), ans = -INF, l, r;
	for (int i = 0; i != 2; ++i, a = b )
		for ( ;a && dist[a] > dist[root]; a = fa[a] )
			if ( belong[root] == belong[a] && belong[a] != -1 )
			{
				l = min(pointpos[root], pointpos[a])+1;
				r = max(pointpos[root], pointpos[a]);
				ans = max( ans, sgtree[belong[root]].getmax(l, r) );
				break;
			}
			else if ( belong[a] == -1 ) ans = max( ans, Ednode[a]);
			else
			{
				ans = max( ans, sgtree[belong[a]].getmax(1,pointpos[a]) );
				a = firptr[belong[a]];
			}
	return ans;
}
void Work()
{
	int i, a, b;
	char tmp[30];
	belong[1] = -1; SelcEdge(1);
	for (i = 1; i <= n; ++i ) if ( belong[i] > 0 ) ++sgtsize[ belong[i] ];
	sgtsize[0] = 1;
	for (i = 0; i <= sgttot; ++i ) //vector下表从0开始
	{
		_st.Init(sgtsize[i]);
		sgtree.push_back(_st);
	}
	fa[1] = 1; CreatSgt(1);
	for (i = 1; i <= sgttot; ++i ) sgtree[i].Build();
	while( true )
	{
		scanf("%s", tmp);
		if ( tmp[0] != 'D' ) scanf("%d%d", &a, &b);
		else return ;
		switch(tmp[0])
		{
			case 'Q': printf("%d\n", find(a, b)); break;
			case 'C': change(b, a); break;
		}
	}
}
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		Init();
		Work();
	}
	return 0;
}