1 const int MAXN=10005;  2 struct Edge  3 {  4     int to, next;  5 }edge[MAXN<<1];  6 int head[MAXN], tot;  7 int top[MAXN];  8 int fa[MAXN];  9 int deep[MAXN]; 10 int num[MAXN]; 11 int p[MAXN]; 12 int fp[MAXN]; 13 int son[MAXN]; 14 int pos; 15 void init() 16 { 17     tot=0; 18     memset(head, -1, sizeof(head)); 19     pos=0; 20     memset(son, -1, sizeof(son)); 21 } 22 void addedge(int u, int v) 23 { 24     edge[tot].to=v; 25     edge[tot].next=head[u]; 26     head[u]=tot++; 27 } 28 void dfs1(int u, int pre, int d) 29 { 30     deep[u]=d; 31     fa[u]=pre; 32     num[u]=1; 33     for(int i=head[u];i!=-1;i=edge[i].next) 34     { 35         int v=edge[i].to; 36         if(v!=pre) 37         { 38             dfs1(v, u, d+1); 39             num[u]+=num[v]; 40             if(son[u]==-1 || num[v]>num[son[u]]) 41                 son[u]=v; 42         } 43     } 44 } 45 void getpos(int u, int sp) 46 { 47     top[u]=sp; 48     p[u]=pos++; 49     fp[p[u]]=u; 50     if(son[u]==-1) 51         return ; 52     getpos(son[u], sp); 53     for(int i=head[u];i!=-1;i=edge[i].next) 54     { 55         int v=edge[i].to; 56         if(v!=son[u] && v!=fa[u]) 57             getpos(v,  v); 58     } 59 } 60  61 struct node 62 { 63     int l, r; 64     int Max; 65 }seg[MAXN*3]; 66 void build(int i, int l, int r) 67 { 68     seg[i].l=l; 69     seg[i].r=r; 70     seg[i].Max=0; 71     if(l==r) 72         return ; 73     int mid=(l+r)>>1; 74     build(i<<1, l, mid); 75     build((i<<1)|1, mid+1, r); 76 } 77 void pushup(int i) 78 { 79     seg[i].Max=max(seg[i<<1].Max, seg[(i<<1)|1].Max); 80 } 81 void update(int i, int k, int val) 82 { 83     if(seg[i].l==k && seg[i].r==k) 84     { 85         seg[i].Max=val; 86         return ; 87     } 88     int mid=(seg[i].l+seg[i].r)>>1; 89     if(k<=mid) 90         update(i<<1, k, val); 91     else 92         update(i<<1|1, k, val); 93     pushup(i); 94 } 95 int query(int i, int l, int r) 96 { 97     if(seg[i].l==l && seg[i].r==r) 98         return seg[i].Max; 99     int mid=(seg[i].l+seg[i].r)>>1;100     if(r<=mid)101         return query(i<<1, l, r);102     else if(l>mid)103         return query((i<<1)|1, l, r);104     else105         return max(query(i<<1, l, mid), query((i<<1)|1, mid+1, r));106 }107 int find(int u, int v)108 {109     int f1=top[u], f2=top[v];110     int tmp=0;111     while(f1!=f2)112     {113         if(deep[f1]<deep[f2])114         {115             swap(f1, f2);116             swap(u, v);117         }118         tmp=max(tmp, query(1, p[f1], p[u]));119         u=fa[f1];120         f1=top[u];121     }122     if(u==v)123         return tmp;124     if(deep[u]>deep[v])125         swap(u, v);126     return max(tmp, query(1, p[son[u]], p[v]));127 }128 129 int e[MAXN][3];130 int main()131 {132     int T;133     scanf("%d", &T);134     while(T--)135     {136         init();137         int n;138         scanf("%d", &n);139         for(int i=0;i<n-1;i++)140         {141             scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);142             addedge(e[i][0], e[i][1]);143             addedge(e[i][1], e[i][0]);144         }145         dfs1(1, 0, 0);146         getpos(1,1);147         build(1, 0, pos-1);148         for(int i=0;i<n-1;i++)149         {150             if(deep[e[i][0]]>deep[e[i][1]])151                 swap(e[i][0], e[i][1]);152             update(1, p[e[i][1]], e[i][2]);153         }154         char op[10];155         while(~scanf("%s", op))156         {157             if(op[0]==‘D‘)158                 break;159             int u, v;160             scanf("%d%d", &u, &v);161             if(op[0]==‘Q‘)162                 printf("%d\n", find(u, v));163             else164                 update(1, p[e[u-1][1]], v);165         }166     }167     return 0;168 }

  1 const int MAXN=50005;  2 struct Edge  3 {  4     int to, next;  5 }edge[MAXN<<1];  6 int head[MAXN], tot;  7 int top[MAXN];  8 int fa[MAXN];  9 int deep[MAXN]; 10 int num[MAXN]; 11 int p[MAXN]; 12 int fp[MAXN]; 13 int son[MAXN]; 14 int pos; 15 void init() 16 { 17     tot=0; 18     memset(head, -1, sizeof(head)); 19     pos=1; 20     memset(son, -1, sizeof(son)); 21 } 22 void addedge(int u, int v) 23 { 24     edge[tot].to=v; 25     edge[tot].next=head[u]; 26     head[u]=tot++; 27 } 28 void dfs1(int u, int pre, int d) 29 { 30     deep[u]=d; 31     fa[u]=pre; 32     num[u]=1; 33     for(int i=head[u];i!=-1;i=edge[i].next) 34     { 35         int v=edge[i].to; 36         if(v!=pre) 37         { 38             dfs1(v, u, d+1); 39             num[u]+=num[v]; 40             if(son[u]==-1 || num[v]>num[son[u]]) 41                 son[u]=v; 42         } 43     } 44 } 45 void getpos(int u, int sp) 46 { 47     top[u]=sp; 48     p[u]=pos++; 49     fp[p[u]]=u; 50     if(son[u]==-1) 51         return ; 52     getpos(son[u], sp); 53     for(int i=head[u];i!=-1;i=edge[i].next) 54     { 55         int v=edge[i].to; 56         if(v!=son[u] && v!=fa[u]) 57             getpos(v,  v); 58     } 59 } 60  61 int lowbit(int x) 62 { 63     return x & (-x); 64 } 65 int c[MAXN]; 66 int n; 67 int sum(int i) 68 { 69     int s=0; 70     while(i>0) 71     { 72         s+=c[i]; 73         i-=lowbit(i); 74     } 75     return s; 76 } 77 void add(int i, int val) 78 { 79     while(i<=n) 80     { 81         c[i]+=val; 82         i+=lowbit(i); 83     } 84 } 85 void change(int u, int v, int val) 86 { 87     int f1=top[u], f2=top[v]; 88     while(f1!=f2) 89     { 90         if(deep[f1]<deep[f2]) 91         { 92             swap(f1, f2); 93             swap(u, v); 94         } 95         add(p[f1], val); 96         add(p[u]+1, -val); 97         u=fa[f1]; 98         f1=top[u]; 99     }100     if(deep[u]>deep[v])101         swap(u, v);102     add(p[u], val);103     add(p[v]+1, -val);104 }105 106 int a[MAXN];107 int main()108 {109     int M, P;110     while(~scanf("%d%d%d", &n, &M, &P))111     {112         init();113         for(int i=1;i<=n;i++)114             scanf("%d", &a[i]);115         while(M--)116         {117             int u, v;118             scanf("%d%d", &u, &v);119             addedge(u, v);120             addedge(v, u);121         }122         dfs1(1, 0, 0);123         getpos(1,1);124         memset(c, 0, sizeof(c));125         for(int i=1;i<=n;i++)126         {127             add(p[i], a[i]);128             add(p[i]+1, -a[i]);129         }130         while(P--)131         {132             char op[10];133             scanf("%s", op);134             if(op[0]==‘Q‘)135             {136                 int x;137                 scanf("%d", &x);138                 printf("%d\n", sum(p[x]));139             }140             else141             {142                 int x, y, z;143                 scanf("%d%d%d", &x, &y, &z);144                 if(op[0]==‘D‘)145                     z=-z;146                 change(x, y, z);147             }148         }149     }150     return 0;151 }