1 #include <cstdio>  2 #include <cstdlib>  3 #include <iostream>  4 #include <cstring>  5 #include <algorithm>  6 using namespace std;  7 typedef unsigned long long ull;  8 typedef long long ll;  9 const int inf = 0x3f3f3f3f; 10 const double eps = 1e-8; 11 const int maxn = 1e4+10; 12 int top[maxn],fa[maxn],son[maxn],dep[maxn],siz[maxn],seg_tree[maxn<<2],head[maxn],pos[maxn]; 13 int edge,tot; 14 struct 15 { 16     int to,next; 17 }e[maxn<<1]; 18 void add(int x,int y) 19 { 20     e[edge].to = y; 21     e[edge].next = head[x]; 22     head[x] = edge++; 23 } 24  25 void dfs(int r) 26 { 27     siz[r] = 1; 28     son[r] = 0; 29     for (int i = head[r]; i > 0; i = e[i].next) 30         if (fa[r] != e[i].to) 31         { 32             dep[e[i].to] = dep[r] + 1; 33             fa[e[i].to] = r; 34             dfs(e[i].to); 35             if (siz[e[i].to] > siz[son[r]]) 36                 son[r] = e[i].to; 37             siz[r] += siz[e[i].to]; 38         } 39 } 40  41 void build(int r,int f) 42 { 43     pos[r] = tot++; 44     top[r] = f; 45     if (son[r] > 0) 46         build(son[r],top[r]); 47     for (int i = head[r]; i > 0; i = e[i].next) 48     { 49         if (fa[r] != e[i].to && son[r] != e[i].to) 50             build(e[i].to,e[i].to); 51     } 52 } 53  54 void update(int l,int r,int o,int x,int v) 55 { 56     if (l == r) 57     { 58         seg_tree[o] = v; 59         return; 60     } 61     int mid = (l + r) >> 1; 62     if (x <= mid) 63         update(l,mid,o<<1,x,v); 64     if (x > mid) 65         update(mid+1,r,o<<1|1,x,v); 66     seg_tree[o] = max(seg_tree[o<<1],seg_tree[o<<1|1]); 67 } 68  69 int query(int l,int r,int o,int ua,int ub) 70 { 71     if (ua <= l && ub >= r) 72         return seg_tree[o]; 73     int mid = (l + r) >> 1; 74     int t1,t2; 75     t1 = t2 = 0; 76     if (ua <= mid) 77         t1 = query(l,mid,o<<1,ua,ub); 78     if (ub > mid) 79         t2 = query(mid+1,r,o<<1|1,ua,ub); 80     return max(t1,t2); 81 } 82  83 int get_max(int ua,int ub) 84 { 85     int f1 = top[ua]; 86     int f2 = top[ub]; 87     int tmp = 0; 88     while (f1 != f2) 89     { 90         if (dep[f1] < dep[f2]) 91             swap(f1,f2),swap(ua,ub); 92         tmp = max(tmp,query(1,tot,1,pos[f1],pos[ua])); 93         ua = fa[f1],f1 = top[ua]; 94     } 95     if (ua == ub) 96         return tmp; 97     if (dep[ua] > dep[ub]) 98         swap(ua,ub); 99     tmp = max(tmp,query(1,tot,1,pos[son[ua]],pos[ub]));100     return tmp;101 }102 103 int d[maxn][3];104 void init()105 {106     int n;107     scanf ("%d",&n);108     memset(dep,0,sizeof(dep));109     memset(son,0,sizeof(son));110     memset(head,0,sizeof(head));111     memset(fa,0,sizeof(fa));112     memset(top,0,sizeof(top));113     int root = (n+1)>>1;114     fa[root] = dep[root] =0;115     tot = edge = 1;116     int a,b,c;117     for (int i = 1; i < n; i++)118     {119         scanf ("%d%d%d",&a,&b,&c);120         add(a,b),add(b,a);121         d[i][0] = a,d[i][1] = b,d[i][2] = c;122     }123     dfs(root);124     build(root,root);125     tot--;126     for (int i = 1; i < n; i++)127     {128         if (dep[d[i][0]] < dep[d[i][1]])129             swap(d[i][1],d[i][0]);130         update(1,tot,1,pos[d[i][0]],d[i][2]);131     }132 133 }134 int main(void)135 {136     #ifndef ONLINE_JUDGE137         freopen("in.txt","r",stdin);138     #endif // ONLINE_JUDGE139     int t;140     scanf ("%d",&t);141     while (t--)142     {143          init();144          char op[10];145          while (scanf ("%s",op),op[0] != ‘D‘)146          {147              int x,y;148              scanf ("%d%d",&x,&y);149              if (op[0] == ‘C‘)150                 update(1,tot,1,pos[d[x][0]],y);151             if (op[0] == ‘Q‘)152                 printf("%d\n",get_max(x,y));153          }154     }155     return 0;156 }