1 #include <cstdio>  2 #include <cstdlib>  3 #include <iostream>  4 #include <algorithm>  5 #include <cstring>  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 = 1e5+10; 12 struct 13 { 14     int to,next; 15 }e[maxn<<1]; 16 int head[maxn],edge; 17 void add(int x,int y) 18 { 19     e[edge].to = y; 20     e[edge].next = head[x]; 21     head[x] = edge++; 22 } 23 int son[maxn],fa[maxn],siz[maxn],dep[maxn]; 24 void dfs(int root) 25 { 26     siz[root] = 1; 27     son[root] = 0; 28     for (int i = head[root]; i > 0; i = e[i].next) 29     { 30         if (fa[root] != e[i].to) 31         { 32             dep[e[i].to] = dep[root] + 1; 33             fa[e[i].to] = root; 34             dfs(e[i].to); 35             if (siz[e[i].to] > siz[son[root]]) 36                 son[root] = e[i].to; 37             siz[root] += siz[e[i].to]; 38         } 39     } 40 } 41 int tot,top[maxn],li[maxn<<2],pos[maxn]; 42 void build(int root,int father) 43 { 44     top[root] = father; 45     pos[root] = tot; 46     li[tot++] = root; 47     if (son[root] > 0) 48         build(son[root],top[root]); 49     for (int i = head[root]; i > 0; i = e[i].next) 50         if (fa[root] != e[i].to && son[root] != e[i].to) 51             build(e[i].to,e[i].to); 52 } 53  54 int minv[maxn<<2],maxv[maxn<<2], tt[maxn],lazy[maxn<<2]; 55 void build_Segtree(int l,int r,int o) 56 { 57     lazy[o] = 0; 58     if (l == r) 59     { 60         minv[o] = tt[li[l]]; 61         maxv[o] =tt[li[l]]; 62         return; 63     } 64     int mid = (l + r) >> 1; 65     build_Segtree(l,mid,o<<1); 66     build_Segtree(mid+1,r,o<<1|1); 67     minv[o] = min(minv[o<<1],minv[o<<1|1]); 68     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]); 69 } 70 char op[10]; 71 int val; 72 inline void push_down(int l,int r,int o) 73 { 74     if (lazy[o]&&l!=r) 75     { 76         maxv[o<<1] = -maxv[o<<1]; 77         minv[o<<1] = -minv[o<<1]; 78         maxv[o<<1|1] = -maxv[o<<1|1]; 79         minv[o<<1|1] = -minv[o<<1|1]; 80         swap(maxv[o<<1],minv[o<<1]); 81         swap(maxv[o<<1|1],minv[o<<1|1]); 82         lazy[o<<1] ^= 1; 83         lazy[o<<1|1] ^= 1; 84         lazy[o] = 0; 85     } 86 } 87 void update(int l,int r,int o,int ua,int ub) 88 { 89     if (ua <= l && ub >= r) 90     { 91         if (op[0] == ‘N‘) 92         { 93             maxv[o] = -maxv[o]; 94             minv[o] = -minv[o]; 95             swap(maxv[o],minv[o]); 96             lazy[o] ^= 1; 97         } 98         if (op[0] == ‘C‘) 99             minv[o] = maxv[o]  = val,lazy[o] = 0;100         return;101     }102     //if (op[0] == ‘N‘)103     push_down(l,r,o);104     int mid = (l + r) >> 1;105     if (ua <= mid)106         update(l,mid,o<<1,ua,ub);107     if (ub > mid)108         update(mid+1,r,o<<1|1,ua,ub);109     minv[o] = min(minv[o<<1],minv[o<<1|1]);110     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);111 }112 113 int query(int l,int r,int o,int ua,int ub)114 {115     if (ua <= l && ub >= r)116         return maxv[o];117     int mid = (l + r) >> 1;118     push_down(l,r,o);119     int t1 = -inf,t2 = -inf;120     if (ua <= mid)121         t1 = query(l,mid,o<<1,ua,ub);122     if (ub > mid)123         t2 = query(mid+1,r,o<<1|1,ua,ub);124     minv[o] = min(minv[o<<1],minv[o<<1|1]);125     maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);126     return max(t1,t2);127 }128 129 int get_max(int ua,int ub)130 {131     int f1 = top[ua];132     int f2 = top[ub];133     int tmp = -inf;134     while (f1 != f2)135     {136         if (dep[f1] < dep[f2])137             swap(ua,ub),swap(f1,f2);138         tmp = max(tmp,query(1,tot,1,pos[f1],pos[ua]));139         ua = fa[f1];140         f1 = top[ua];141     }142     if (ua == ub)143         return tmp;144     if (dep[ua]  > dep[ub])145         swap(ua,ub);146     return tmp = max(tmp,query(1,tot,1,pos[son[ua]],pos[ub]));147 }148 void get_negate(int ua,int ub)149 {150     int f1 = top[ua];151     int f2 = top[ub];152     while (f1 != f2)153     {154         if (dep[f1] < dep[f2])155             swap(ua,ub),swap(f1,f2);156         update(1,tot,1,pos[f1],pos[ua]);157         ua = fa[f1];158         f1 = top[ua];159     }160     if (dep[ua] > dep[ub])161         swap(ua,ub);162     if (ua == ub)163         return;164     update(1,tot,1,pos[son[ua]],pos[ub]);165 }166 167 int d[maxn][3];168 void init()169 {170     int root,n;171     scanf ("%d",&n);172     root = (n + 1) >> 1;173     edge = tot = 1;174     memset(siz,0,sizeof(siz));175     memset(head,0,sizeof(head));176     fa[root] = dep[root] = 0;177     for (int i = 1; i < n; i++)178     {179         scanf ("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);180         add(d[i][1],d[i][0]);181         add(d[i][0],d[i][1]);182     }183     dfs(root);184     build(root,root);185     build_Segtree(1,tot,1);186     op[0] = ‘C‘;187     for (int i = 1; i < n; i++)188     {189         if (dep[d[i][0]] < dep[d[i][1]])190             swap(d[i][0],d[i][1]);191         tt[d[i][0]] = val = d[i][2];192         update(1,tot,1,pos[d[i][0]],pos[d[i][0]]);193     }194 }195 int main(void)196 {197     freopen("in.txt","r",stdin);198     int t;199     scanf ("%d",&t);200     while (t--)201     {202         init();203         while (scanf ("%s",op),op[0] != ‘D‘)204         {205             int x,y;206             scanf ("%d%d",&x,&y);207             if (op[0] == ‘Q‘&&x!=y)208                 printf("%d\n",get_max(x,y));209             if (op[0] == ‘Q‘ && x == y)210                 printf("0\n");211             if (op[0] == ‘C‘)212             {213                 val = y;214                 update(1,tot,1,pos[d[x][0]],pos[d[x][0]]);215             }216             if (op[0] == ‘N‘&&x!=y)217                 get_negate(x,y);218         }219     }220     return 0;221 }222 223 224 /*225 1226 11227 2 1 1228 2 4 2229 2 3 3230 1 5 4231 3 6 5232 3 7 6233 7 8 7234 4 9 8235 9 10 9236 10 11 10237 N 2 10238 Query 4 10239 DONE240 241 */