1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <set> 5 #include <queue> 6 #include <algorithm> 7 #include <cmath> 8 #include <vector> 9 using namespace std; 10 #define N 10010 11 #define ls o<<1 12 #define rs o<<1|1 13 #define define_m int m=(l+r)>>1 14 int maxn[N<<2] , dis[N]; 15 16 struct Edge{ 17 int x,y,d; 18 Edge(int x=0 , int y=0 , int d=0):x(x),y(y),d(d){} 19 }; 20 21 vector<Edge> v[N]; 22 int fa[N] , son[N] , sz[N] , top[N] , dep[N] , id[N] , k; 23 int n , st[N] , en[N] , d[N] , val; 24 char str[20]; 25 26 void dfs(int u , int f , int d) 27 { 28 fa[u] = f; 29 sz[u] = 1 , dep[u]=d , son[u]=0; 30 int len = v[u].size(); 31 int maxn = 0; 32 for(int i=0 ; i<len ; i++){ 33 int to=v[u][i].y; 34 if(to==f) continue; 35 dfs(to,u,d+1); 36 sz[u]+=sz[to]; 37 if(sz[to]>maxn){ 38 son[u]=to; 39 maxn = sz[to]; 40 } 41 } 42 } 43 44 void dfs1(int u , int f , int head) 45 { 46 int l=v[u].size(); 47 top[u] = head; 48 if(son[u]){ 49 id[son[u]] = ++k; 50 dfs1(son[u] , u , head); 51 } 52 for(int i=0 ; i<l ; i++){ 53 int to = v[u][i].y; 54 if(to==f || to==son[u]) continue; 55 id[to] = ++k; 56 dfs1(to , u , to); 57 } 58 } 59 60 void push_up(int o) 61 { 62 maxn[o] = max(maxn[ls] , maxn[rs]); 63 } 64 65 void build(int o , int l , int r) 66 { 67 if(l==r){ 68 maxn[o] = dis[l]; 69 return ; 70 } 71 define_m; 72 build(ls , l , m); 73 build(rs , m+1 , r); 74 push_up(o); 75 } 76 77 void update(int o , int l , int r , int pos, int v) 78 { 79 if(l==r && l==pos){ 80 maxn[o] = v; 81 return; 82 } 83 define_m; 84 if(m>=pos) update(ls , l , m , pos , v); 85 else update(rs , m+1 , r , pos , v); 86 push_up(o); 87 } 88 89 int query(int o , int l , int r , int s , int t) 90 { 91 // cout<<"query: "<<o<<" "<<l<<" "<<r<<" "<<s<<" "<<t<<endl; 92 if(l>=s && r<=t){ 93 return maxn[o]; 94 } 95 int ans = 0; 96 define_m; 97 if(m>=s) ans = max(ans , query(ls , l , m , s , t)); 98 if(m<t) ans= max(ans , query(rs , m+1 , r , s , t)); 99 return ans; 100 } 101 102 int CalPath(int u , int v) 103 { 104 int top1=top[u] , top2=top[v]; 105 int ans = 0; 106 while(top1 != top2){ 107 if(dep[top1]<dep[top2]){ 108 swap(top1 , top2); 109 swap(u , v); 110 } 111 ans = max(ans , query(1 , 1 , k , id[top1] , id[u])); 112 u=fa[top1]; 113 top1=top[u]; 114 } 115 if(u!=v){ 116 if(dep[u]<dep[v]){ 117 swap(u,v); 118 } 119 ans=max(ans,query(1,1,k,id[son[v]],id[u])); 120 // cout<<"in: "<<id[u]<<" "<<id[son[v]]<<endl; 121 // cout<<"u: "<<u<<" v: "<<v<<" "<<ans<<endl; 122 } 123 return ans; 124 } 125 126 int main() 127 { 128 // freopen("a.in" , "r" , stdin); 129 int T; 130 scanf("%d" , &T); 131 while(T--) 132 { 133 scanf("%d" , &n); 134 for(int i=1 ; i<=n ; i++) v[i].clear(); 135 for(int i=1 ; i<n ; i++){ 136 scanf("%d%d%d" , &st[i] , &en[i] , &d[i]); 137 v[st[i]].push_back(Edge(st[i],en[i],d[i])); 138 v[en[i]].push_back(Edge(en[i],st[i],d[i])); 139 } 140 k=0; 141 dfs(1,0,1); 142 dfs1(1,0,1); 143 for(int i=1 ; i<n ; i++){ 144 int ID; 145 if(st[i] != fa[en[i]]) ID = id[st[i]]; 146 else ID = id[en[i]]; 147 // cout<<"ID: "<<ID<<endl; 148 dis[ID] = d[i]; 149 } 150 /* for(int i=1 ; i<=n ; i++){ 151 cout<<fa[i]<<" "<<son[i]<<" "<<dep[i]<<" "<<sz[i]<<" "<<top[i]<<" "<<id[i]<<endl; 152 if(i<n) cout<<"i: "<<dis[i]<<endl; 153 }*/ 154 build(1,1,k); 155 // cout<<"sum: "<<sum[1]<<" "<<sum[2]<<" "<<sum[3]<<endl; 156 while(scanf("%s" , str) && str[0]!='D'){ 157 int t1 , t2; 158 scanf("%d%d" , &t1 , &t2); 159 if(str[0] == 'C'){ 160 int ID; 161 if(st[t1] != fa[en[t1]]) ID = id[st[t1]]; 162 else ID = id[en[t1]]; 163 // cout<<"ID: "<<ID<<endl; 164 update(1,1,k,ID,t2); 165 } 166 else{ 167 int ans = CalPath(t1,t2); 168 printf("%d " , ans); 169 } 170 } 171 } 172 return 0; 173 }