#include<cstdio>#include<iostream>#include<cstring>using namespace std;const int N=210000;const int inf=0x3fffffff;int son[N],father[N],sz[N],head[N],num;int ti[N],idx,dep[N],top[N];struct edge{    int ed,nxt;}e[N*3];struct Edge{    int x,y,v;}E[N*2];int max(int a,int b){    if(a>b)return a;    return b;}void addedge(int x,int y){    e[++num].ed=y;e[num].nxt=head[x];head[x]=num;    e[++num].ed=x;e[num].nxt=head[y];head[y]=num;}void dfs_find(int u,int fa){//处理每棵子树大小和重儿子     sz[u]=1;dep[u]=dep[fa]+1;son[u]=0;father[u]=fa;    for(int i=head[u];i;i=e[i].nxt){        int v=e[i].ed;        if(v==fa)continue;        dfs_find(v,u);        sz[u]+=sz[v];        if(sz[son[u]]<sz[v])son[u]=v;    }}void dfs_time(int u,int fa){    ti[u]=idx++;    top[u]=fa;    if(son[u]!=0)dfs_time(son[u],top[u]);//处理同重链上点的top     for(int i=head[u];i;i=e[i].nxt){        int v=e[i].ed;        if(v==father[u]||v==son[u])continue;//枚举到了同一重链上的点就跳过         dfs_time(e[i].ed,e[i].ed);    }}struct tree{    int l,r,v;}T[N<<2];void buildtree(int l,int r,int id){    T[id].l=l;T[id].r=r;T[id].v=-inf;    if(l==r)return;    int mid=(l+r)>>1;    buildtree(l,mid,id*2);    buildtree(mid+1,r,id*2+1);}void update(int id,int cp,int v){    if(T[id].l==T[id].r){T[id].v=v;return;}    int mid=(T[id].l+T[id].r)>>1;    if(mid>=cp)update(id*2,cp,v);    if(mid<cp)update(id*2+1,cp,v);    T[id].v=max(T[id*2].v,T[id*2+1].v);}int query(int l,int r,int id){    if(T[id].r==r&&T[id].l==l)return T[id].v;    int mid=(T[id].l+T[id].r)>>1;    if(mid>=r)return query(l,r,id*2);    else if(mid<l)return query(l,r,id*2+1);    else return max(query(l,mid,id*2),query(mid+1,r,id*2+1));}int lca(int x,int y){    int ans=-inf;    while(top[x]!=top[y]){        if(dep[top[x]]<dep[top[y]])swap(x,y);        ans=max(ans,query(ti[top[x]],ti[x],1));        x=father[top[x]];    }    if(dep[x]>dep[y])swap(x,y);    if(x!=y)ans=max(ans,query(ti[x]+1,ti[y],1));    return ans;}int main(){    int n,t,x,y,v,j;    char str[100];    scanf("%d",&t);    while(t--){        memset(head,0,sizeof(head));        num=0;scanf("%d",&n);        for(int i=1;i<n;i++){            scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].v);            addedge(E[i].x,E[i].y);        }        dep[1]=0;sz[0]=0;idx=1;        dfs_find(1,1);        dfs_time(1,1);        buildtree(2,n,1);        for(int i=1;i<n;i++){            if(dep[E[i].x]<dep[E[i].y])swap(E[i].x,E[i].y);            update(1,ti[E[i].x],E[i].v);        }        while(true){            scanf("%s",str);            if(str[0]==‘D‘)break;            else if(str[0]==‘Q‘){                scanf("%d%d",&x,&y);                printf("%d\n",lca(x,y));            }            else if(str[0]==‘C‘){                scanf("%d%d",&j,&v);                update(1,ti[E[j].x],v);            }        }    }    return 0;}