You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word “DONE” ends the test case.

For each “QUERY” instruction, output the result on a separate line.

#include <iostream>#include <algorithm>#include <cstdio>#include <queue>#include <cmath>#include <map>#include <iterator>#include <cstring>#include <string>using namespace std;#define INF 0x7fffffff#define ll long long#define N 100010struct Edge2{    int a,b,c;}s[N<<1];struct Edge{    int to,next;}edge[N<<1];int head[N],tot;int num[N];int pos;int fa[N];int son[N];int p[N];int fp[N];int deep[N];int size[N];int top[N];int n;void init(){    tot=0;    pos=1;    memset(head,-1,sizeof(head));    memset(son,-1,sizeof(son));}void add(int x,int y){    edge[tot].to=y;    edge[tot].next=head[x];    head[x]=tot++;}void dfs1(int now,int pre,int d){    deep[now]=d;    fa[now]=pre;    size[now]=1;    for(int i=head[now];i!=-1;i=edge[i].next)    {        int next=edge[i].to;        if(next!=pre)        {            dfs1(next,now,d+1);            size[now]+=size[next];            if(son[now]==-1 || size[next]>size[son[now]])            {                son[now]=next;            }        }    }}void dfs2(int now,int tp){    top[now]=tp;    p[now]=pos++;    fp[p[now]]=now;    if(son[now]==-1) return;    dfs2(son[now],tp);    for(int i=head[now];i!=-1;i=edge[i].next)    {        int next=edge[i].to;        if(next!=son[now]&&next!=fa[now])        {            dfs2(next,next);        }    }}int mx[N<<2];int mi[N<<2];int col[N<<2];void pushup(int rt){    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);    mi[rt]=min(mi[rt<<1],mi[rt<<1|1]);}void pushdown(int rt){    if(col[rt])    {        col[rt<<1]^=1;        col[rt<<1|1]^=1;        mx[rt<<1]=-mx[rt<<1];        mi[rt<<1]=-mi[rt<<1];        swap(mx[rt<<1],mi[rt<<1]);        mx[rt<<1|1]=-mx[rt<<1|1];        mi[rt<<1|1]=-mi[rt<<1|1];        swap(mx[rt<<1|1],mi[rt<<1|1]);        col[rt]=0;    }}void build(int l,int r,int rt){    col[rt]=0;    if(l==r)    {        mi[rt]=mx[rt]=num[fp[l]];        return;    }    int m=(l+r)>>1;    build(l,m,rt<<1);    build(m+1,r,rt<<1|1);    pushup(rt);}void update(int l,int r,int rt,int pos,int val){    if(l==r)    {        mi[rt]=mx[rt]=val;        return;    }    pushdown(rt);    int m=(l+r)>>1;    if(pos<=m) update(l,m,rt<<1,pos,val);    else update(m+1,r,rt<<1|1,pos,val);    pushup(rt);}void update2(int l,int r,int rt,int L,int R){    if(l==L && R==r)    {        mx[rt]=-mx[rt];        mi[rt]=-mi[rt];        swap(mx[rt],mi[rt]);        col[rt]^=1;        return;    }    pushdown(rt);    int m=(l+r)>>1;    if(R<=m) update2(l,m,rt<<1,L,R);    else if(L>m) update2(m+1,r,rt<<1|1,L,R);    else    {        update2(l,m,rt<<1,L,m);        update2(m+1,r,rt<<1|1,m+1,R);    }    pushup(rt);}int query(int l,int r,int rt,int L,int R){    if(l==L && r==R)    {        return mx[rt];    }    pushdown(rt);    int m=(l+r)>>1,ans=-INF;    if(L>m) return ans=max(ans,query(m+1,r,rt<<1|1,L,R));    else if(R<=m) ans=max(ans,query(l,m,rt<<1,L,R));    else return ans=max(ans,max(query(l,m,rt<<1,L,m),query(m+1,r,rt<<1|1,m+1,R)));    return ans;}int convert(int pos){    int a=s[pos].a;    int b=s[pos].b;    if(deep[a]>deep[b]) return a;    return b;}void pre_solve(){    memset(num,-1,sizeof(num));    for(int i=1;i<n;i++)    {        num[convert(i)]=s[i].c;    }}void change2(int x,int y){    int f1=top[x];    int f2=top[y];    while(f1!=f2)    {        if(deep[f1]<deep[f2])        {            swap(x,y);            swap(f1,f2);        }        update2(1,n,1,p[f1],p[x]);        x=fa[f1];        f1=top[x];    }    if(x==y) return;    if(deep[x]>deep[y]) swap(x,y);    update2(1,n,1,p[x]+1,p[y]);}int change(int x,int y){    int ans=-INF;    int f1=top[x];    int f2=top[y];    while(f1!=f2)    {        if(deep[f1]<deep[f2])        {            swap(x,y);            swap(f1,f2);        }        ans=max(ans,query(1,n,1,p[f1],p[x]));        x=fa[f1];        f1=top[x];    }    if(x==y) return ans;    if(deep[x]>deep[y]) swap(x,y);    ans=max(ans,query(1,n,1,p[x]+1,p[y]));    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        init();        scanf("%d",&n);        for(int i=1;i<n;i++)        {            scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);            add(s[i].a,s[i].b);            add(s[i].b,s[i].a);        }        dfs1(1,0,0);        dfs2(1,1);        pre_solve();        build(1,n,1);        while(1)        {            int a,b;            char op[10];            scanf("%s",op);            if(op[0]==‘D‘) break;            scanf("%d%d",&a,&b);            if(op[0]==‘C‘)            {                a=convert(a);                update(1,n,1,p[a],b);            }            else if(op[0]==‘N‘)            {                change2(a,b);            }            else            {                printf("%d\n",change(a,b));            }        }    }    return 0;}