//Accepted 2280 KB 688 ms
/*
source:poj3237
time :2015.5.29
by :songt
*/
/*题解:
树链剖分
基于边权,路径查询最大值
线段树开到3倍RE,开到4倍AC
*/
#include <cstdio>
#include <cstring>
;
const int inf = 0x3f3f3f3f;
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
struct Edge
{
int u,v;
Edge(){}
Edge(int u,int v):u(v),v(v){}
}edge[*imax_n];
int head[imax_n];
*imax_n];
int tot;
void addEdge(int u,int v)
{
edge[tot]=Edge(u,v);
next[tot]=head[u];
head[u]=tot++;
}
int fa[imax_n],deep[imax_n],num[imax_n],son[imax_n];
int p[imax_n],fp[imax_n],top[imax_n];
int pos;
void init()
{
memset(head,-,sizeof(head));
memset(next,-,sizeof(next));
tot=;
memset(son,-,sizeof(son));
pos=;
}
void dfs1(int u,int pre,int depth)
{
fa[u]=pre;
deep[u]=depth;
num[u]=;
;i=next[i])
{
int v=edge[i].v;
if (v!=pre)
{
dfs1(v,u,depth+);
num[u]+=num[v];
|| num[son[u]]<num[v])
son[u]=v;
}
}
}
void dfs2(int u,int sp)
{
p[u]=pos++;
fp[p[u]]=u;
top[u]=sp;
) return ;
dfs2(son[u],sp);
;i=next[i])
{
int v=edge[i].v;
if (v!=fa[u] && v!=son[u])
{
dfs2(v,v);
}
}
}
struct Tree
{
int l,r;
int tmax,tmin;
int rev;
}f[imax_n*];
void build(int t,int l,int r)
{
f[t].l=l;
f[t].r=r;
f[t].tmax=f[t].tmin=;
f[t].rev=;
if (l==r)
{
return ;
}
;
build(*t,l,mid);
build(*t+,mid+,r);
}
void push_down(int t)
{
f[*t].rev^=;
f[*t+].rev^=;
*t].tmax;
f[*t].tmax=-f[*t].tmin;
f[*t].tmin=-tmp;
tmp=f[*t+].tmax;
f[*t+].tmax=-f[*t+].tmin;
f[*t+].tmin=-tmp;
f[t].rev=;
}
void push_up(int t)
{
f[t].tmax=max(f[*t].tmax,f[*t+].tmax);
f[t].tmin=min(f[*t].tmin,f[*t+].tmin);
}
void update(int t,int k,int value)
{
if (f[t].l==k && f[t].r==k)
{
f[t].tmax=f[t].tmin=value;
return ;
}
if (f[t].rev) push_down(t);
;
*t,k,value);
*t+,k,value);
push_up(t);
}
void reverse(int t,int l,int r)
{
if (f[t].l==l && f[t].r==r)
{
f[t].rev^=;
int tmp=f[t].tmax;
f[t].tmax=-f[t].tmin;
f[t].tmin=-tmp;
return ;
}
if (f[t].rev) push_down(t);
;
*t,l,r);
else
{
*t+,l,r);
else
{
reverse(*t,l,mid);
reverse(*t+,mid+,r);
}
}
push_up(t);
}
int query(int t,int l,int r)
{
if (f[t].l==l && f[t].r==r)
{
return f[t].tmax;
}
if (f[t].rev) push_down(t);
;
*t,l,r);
else
{
*t+,l,r);
*t,l,mid),query(*t+,mid+,r));
}
}
void Re(int u,int v)
{
int f1=top[u],f2=top[v];
while (f1!=f2)
{
if (deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
reverse(,p[f1],p[u]);
u=fa[f1];
f1=top[u];
}
if (u==v) return ;
if (deep[u]>deep[v]) swap(u,v);
reverse(,p[son[u]],p[v]);
}
int find(int u,int v)
{
int f1=top[u],f2=top[v];
int ans=-inf;
while (f1!=f2)
{
if (deep[f1]<deep[f2])
{
swap(f1,f2);
swap(u,v);
}
ans=max(ans,query(,p[f1],p[u]));
u=fa[f1];
f1=top[u];
}
if (u==v) return ans;
if (deep[u]>deep[v]) swap(u,v);
ans=max(ans,query(,p[son[u]],p[v]));
//printf("query %d %d\n",son[u],v);
return ans;
}
];
int n,m;
int u,v,c;
];
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
init();
;i<n-;i++)
{
scanf(],&e[i][],&e[i][]);
addEdge(e[i][],e[i][]);
addEdge(e[i][],e[i][]);
}
dfs1(,,);
dfs2(,);
build(,,pos-);
;i<n-;i++)
{
]]<deep[e[i][]]) swap(e[i][],e[i][]);
update(,p[e[i][]],e[i][]);
}
)
{
) break;
scanf("%d%d",&u,&v);
]=='Q')
{
printf("%d\n",find(u,v));
}
]=='N')
{
Re(u,v);
}
]=='C')
{
update(,p[e[u-][]],v);
}
}
}
;
}