Description

Input:

1

3

1 2 1

2 3 2

QUERY 1 2

CHANGE 1 3

QUERY 1 2

DONE

Output:

1

3

Hint

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<vector>

 #define lc rt<<1

 #define rc rt<<1|1

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int T;

 int n,m;

 int pe[mxn][];

 struct edge{

     int v,nxt,w;

 }e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v,int d){

     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=d;hd[u]=mct;return;

 }

 struct node{

     int f,son;

     int top,size;

     int w,e,dep;

 }tr[mxn];

 int sz=;

 void DFS1(int u){

     tr[u].size=;

     tr[u].son=;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(v==tr[u].f)continue;

         tr[v].dep=tr[u].dep+;

         tr[v].f=u;

         DFS1(v);

         tr[u].size+=tr[v].size;

         if(tr[v].size>tr[tr[u].son].size)tr[u].son=v;

     }

     return;

 }

 void DFS2(int u,int top){

     tr[u].top=top;

     tr[u].w=++sz;

     if(tr[u].son){

         DFS2(tr[u].son,top);

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(v!=tr[u].f && v!=tr[u].son){

                 DFS2(v,v);

             }

         }

     }

     tr[u].e=sz;

 }

 //

 struct segtree{

     int mx;

 }st[mxn<<];

 void change(int p,int v,int l,int r,int rt){

     if(l==r){

         if(l==p)

             st[rt].mx=v;

         return;

     }

     int mid=(l+r)>>;

     if(p<=mid)change(p,v,l,mid,lc);

     else change(p,v,mid+,r,rc);

     st[rt].mx=max(st[lc].mx,st[rc].mx);

     return;

 }

 int qmx(int L,int R,int l,int r,int rt){

     if(L<=l && r<=R)return st[rt].mx;

     int mid=(l+r)>>;

     int res=-1e9;

     if(L<=mid)res=max(res,qmx(L,R,l,mid,lc));

     if(R>mid)res=max(res,qmx(L,R,mid+,r,rc));

     return res;

 }

 int query(int x,int y){

     int res=-1e9;

     while(tr[x].top!=tr[y].top){

         if(tr[tr[x].top].dep<tr[tr[y].top].dep)swap(x,y);

         res=max(res,qmx(tr[tr[x].top].w,tr[x].w,,n,));

         x=tr[tr[x].top].f;

     }

     if(tr[x].dep>tr[y].dep)swap(x,y);

     if(x!=y)res=max(res,qmx(tr[tr[x].son].w,tr[y].w,,n,));//不经过公共祖先

     return res;

 }

 //

 void init(){

     memset(st,,sizeof st);

     memset(hd,,sizeof hd);

     mct=;sz=;

 }

 int main(){

     T=read();

     int i,j,x,y,z;

     while(T--){

         init();

         n=read();

         int rt=n/+;

         for(i=;i<n;i++){

             x=read();y=read();z=read();

             add_edge(x,y,z);

             add_edge(y,x,z);

             pe[i][]=x;pe[i][]=y;pe[i][]=z;//记录边信息

         }

         tr[rt].f=tr[rt].son=tr[rt].dep=;

         DFS1(rt);

         DFS2(rt,rt);

         for(i=;i<n;i++){

             if(tr[pe[i][]].dep>tr[pe[i][]].dep)swap(pe[i][],pe[i][]);

             change(tr[pe[i][]].w,pe[i][],,n,);

         }

         char op[];

         while(scanf("%s",op) && op[]!='D'){

             if(op[]=='Q'){

                 x=read();y=read();

                 printf("%d\n",query(x,y));

             }

             if(op[]=='C'){

                 x=read();y=read();

                 change(tr[pe[x][]].w,y,,n,);

             }

         }

     }

     return ;

 }