1 #include <iostream>  2 #include <cstdio>  3 #include <cstdlib>  4 #include <cmath>  5 #include <algorithm>  6 #include <cstring>  7 #include <stack>  8 #include <cctype>  9 #include <queue> 10 #include <string> 11 #include <vector> 12 #include <set> 13 #include <map> 14 #include <climits> 15 #define lson rt<<1,l,mid 16 #define rson rt<<1|1,mid+1,r 17 #define fi first 18 #define se second 19 #define ping(x,y) ((x-y)*(x-y)) 20 #define mst(x,y) memset(x,y,sizeof(x)) 21 #define mcp(x,y) memcpy(x,y,sizeof(y)) 22 using namespace std; 23 #define gamma 0.5772156649015328606065120 24 #define MOD 1000000007 25 #define inf 0x3f3f3f3f 26 #define N 10050 27 #define maxn 30010 28 typedef pair<int,int> PII; 29 typedef long long LL; 30 LL read(){ 31     LL x=0,f=1;char ch=getchar(); 32     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 33     while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} 34     return x*f; 35 } 36 int n,m,k,head[N],hcnt,rt; 37 char str[11]; 38 struct Node{ 39     int to,nxt,v; 40 }node[maxn]; 41 struct Edge{ 42     int x,y,v; 43 }edge[maxn]; 44 int seg[N<<2]; 45  46 int siz[N];  ///当前节点保存的儿子数 47 int top[N];  ///当前节点所在链的顶端节点 48 int son[N];  ///保存重儿子 49 int dep[N];  ///当前节点深度 50 int fa[N];   ///当前节点的父亲 51 int id[N];   ///用来保存树中每个节点剖分后的新编号 52 int posi[N]; ///在线段树中的位置 53 int tid,pos; 54  55 ///树链剖分 56 void dfs1(int u,int f,int deep){ ///找重边 57     dep[u]=deep; 58     fa[u]=f; 59     siz[u]=1; 60     for(int i=head[u];~i;i=node[i].nxt){ 61         int e=node[i].to; 62         if(e==f)continue; 63         dfs1(e,u,deep+1); 64         siz[u]+=siz[e]; 65         if(!son[u]||siz[son[u]]<siz[e]) 66             son[u]=e; 67     } 68 } 69 void dfs2(int u,int tp){   ///连重边成重链 70     top[u]=tp; 71     id[u]=++tid; 72     posi[id[u]]=u; 73     if(!son[u])return; 74     dfs2(son[u],tp); 75     for(int i=head[u];~i;i=node[i].nxt){ 76         int e=node[i].to; 77         if(e!=son[u]&&e!=fa[u]) 78             dfs2(e,e); 79     } 80 } 81  82 ///线段树 83 void build(int rt,int l,int r){ 84     seg[rt]=-inf; 85     if(l==r) return; 86     int mid=l+r>>1; 87     build(lson); build(rson); 88     seg[rt]=max(seg[rt<<1],seg[rt<<1|1]); 89 } 90  91 void add(int rt,int l,int r,int v){ 92     if(l==r){ 93         seg[rt]=v; 94         return; 95     } 96     int mid=l+r>>1; 97     if(pos<=mid)add(lson,v); 98     else add(rson,v); 99     seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);100 }101 int query(int rt,int l,int r,int L,int R){102     if(L<=l&&r<=R){return seg[rt];}103     int mid=l+r>>1;104     int temp=INT_MIN;105     if(L<=mid)temp=max(temp,query(lson,L,R));106     if(R>mid) temp=max(temp,query(rson,L,R));107     return temp;108 }109 110 void ini(){111     mst(head,-1);hcnt=tid=0;mst(seg,0);112     mst(son,0);mst(siz,0);113 }114 void add(int x,int y,int v){115     node[hcnt].to=y,node[hcnt].nxt=head[x],node[hcnt].v=v,head[x]=hcnt++;116     node[hcnt].to=x,node[hcnt].nxt=head[y],node[hcnt].v=v,head[y]=hcnt++;117 }118 int lca(int x,int y){119     int ans=-inf;120     while(top[x]!=top[y]){121         if(dep[top[x]]<dep[top[y]])swap(x,y);122         ans=max(ans,query(1,1,n,id[top[x]],id[x]));123         x=fa[top[x]];124     }125     if(dep[x]>dep[y])swap(x,y);126     if(x!=y)ans=max(ans,query(1,1,n,id[x]+1,id[y]));127     return ans;128 }129 int main(){130     //freopen("in.txt","r",stdin);131     int i,j,group,x,y,v,Case=0;132     group=read();133     while(group--){134         ini();135         n=read();136         for(i=1;i<n;++i){137             scanf("%d%d%d",&x,&y,&v);138             edge[i].x=x,edge[i].y=y,edge[i].v=v;139             add(x,y,v);140         }141         dfs1(1,1,1);142         dfs2(1,1);143         build(1,1,n);144         for(i=1;i<n;i++){145             if(dep[edge[i].x]<dep[edge[i].y])146                 swap(edge[i].x,edge[i].y);147             pos=id[edge[i].x];148             add(1,1,n,edge[i].v);149         }150         while(scanf("%s",str)!=EOF){151             if(str[0]==‘D‘)break;152             x=read();y=read();153             if(str[0]==‘Q‘){154                 printf("%d\n",lca(x,y));155             }156             else{157                 pos=id[edge[x].x];158                 add(1,1,n,y);159             }160         }161         printf("\n");162     }163     return 0;164 }