#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define LB 15
vector<int> ed[11007],cost[11007];
pair<int,int> ed_num[11005];
int posHLD[11005],ChainHead[11005]={0},height[11004],lca_q[LB][11005];//,NodeNum[10005];
int ChainNum[11005],counter,subsize[11005],seg[60005],chain_ed[11005],ChainNo;
int precompute(int node)
{
int ans=1;
for(int i=0;i<ed[node].size();i++)
{
int x=ed[node][i];
if(lca_q[0][node]!=x)
{
lca_q[0][x]=node;
ans+=precompute(x);
}
}
subsize[node]=ans;
return ans;
}
void HLD_init(int node,int h,int costs)
{
int special_child=0,mx=0,mxi=0,mxii;
height[node]=h;
if(!ChainHead[ChainNo])
{
ChainHead[ChainNo]=node;
//counter=1;
}
posHLD[node]=counter;
//NodeNum[counter]=node;
//chain_size[ChainNo]=counter;
chain_ed[counter]=costs;//Child side of the edge keeps the cost of the edge
counter++;
//cout<<counter<<"\n";
ChainNum[node]=ChainNo;
for(int i=0;i<ed[node].size();i++)
{
int x=ed[node][i];
if(lca_q[0][node]!=x)
{
if(mx<subsize[x])
{
mx=subsize[x];
mxi=x;
mxii=i;
}
}
}
special_child=mxi;
if(special_child)
HLD_init(special_child,h+1,cost[node][mxii]);
for(int i=0;i<ed[node].size();i++)
{
int x=ed[node][i];
if(lca_q[0][node]!=x&&x!=special_child)
{
ChainNo++;
//connector[chain][(*ch)]=connector[(*ch)][chain]=cost[node][i];
HLD_init(x,h+1,cost[node][i]);
}
}
return;
}
int lca_tree(int a,int b)
{
int ha,hb,diff;
if(a==b)
return a;
if(height[a]>height[b])
{
a=a^b;
b=a^b;
a=a^b;
}
ha=height[a],b=height[b];
diff=hb-ha;
for(int i=0;i<LB;i++)
if((diff>>i)&1)
a=lca_q[i][a];
if(a==b)return a;
for(int i=LB-1;i>=0;i--)
if(lca_q[i][a]!=lca_q[i][b])
{
a=lca_q[i][a];
b=lca_q[i][b];
}
return lca_q[0][a];
}
void build_chain(int node,int l,int r)
{
if(l==r)
{
seg[node]=chain_ed[r];
return;
}
int mid=(l+r)>>1,child=node<<1;//,n1=NodeNum[mid],n2=NodeNum[mid+1];
build_chain(child,l,mid);
build_chain(child+1,mid+1,r);
seg[node]=max(seg[child],seg[child+1]);
//seg[chain][node]=max(seg[chain][node],chain_ed[chain][mid]);
//cout<<l<<" "<<r<<"\n";
//cout<<seg[node]<<"\n";
return;
}
int query(int node,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)
{
return seg[node];
}
int mid=(l+r)>>1,child=node<<1,ans=0;//,n1=NodeNum[mid],n2=NodeNum[mid+1];
if(mid>=ql) ans=query(child,l,mid,ql,qr);
if(mid+1<=qr) ans=max(ans,query(child+1,mid+1,r,ql,qr));
//if(mid>=ql&&mid+1<=qr)
//ans=max(ans,chain_ed[chain][mid]);
return ans;
}
void update(int node,int l,int r,int a,int val)
{
//if((l==a&&l==r)||(l==b&&l==r))
//return;
//if(l)
//cout<<l<<" "<<r<<"\n";
//getchar();
if(l==r)
{
if(l==a)
{
chain_ed[l]=val;
seg[node]=val;
}
return ;
}
int mid=(l+r)>>1,child=node<<1,flag=0;
if(mid>=a) {
update(child,l,mid,a,val);
//flag++;
}
if(mid+1<=a) {
update(child+1,mid+1,r,a,val);
//flag++;
}
seg[node]=max(seg[child],seg[child+1]);
//if(flag==2)
//{
//chain_ed[chain][mid]=val;
//seg[chain][node]=max(seg[chain][node],val);
//return;
//}
return;
}
int sub_query(int u,int v)
{
int uchain=ChainNum[u],vchain=ChainNum[v],mx=0;
while(1)
{
//cout<<posHLD[u]<<" "<<posHLD[v]<<"\n";
if(uchain==vchain)
{
int ans=0;
if(u!=v)
ans=query(1,1,counter-1,posHLD[v]+1,posHLD[u]);
mx=max(mx,ans);
break;
}
int ans=query(1,1,counter-1,posHLD[ChainHead[uchain]],posHLD[u]);
if(ans>mx)
mx=ans;
u=ChainHead[uchain];
u=lca_q[0][u];
//mx=max(mx,connector[uchain][u]);
uchain=ChainNum[u];
}
return mx;
}
//LCA calculation remaining
int HLD_query(int a,int b)
{
int lca=lca_tree(a,b);
//cout<<lca<<"Sub Query\n";
return max(sub_query(a,lca),sub_query(b,lca));
}
int up_use(int val,int num)
{
int a=ed_num[num].first,b=ed_num[num].second;
if(a==lca_q[0][b])
update(1,1,counter-1,posHLD[b],val);
else update(1,1,counter-1,posHLD[a],val);
}
int main()
{
int t;
scanf("%d\n",&t);
while(t--)
{
int n;
//getchar();
scanf("%d",&n);
counter=1,ChainNo=1;
for(int i=1;i<n;i++)
{
ed[i].clear();
cost[i].clear();
ChainHead[i]=0;
for(int j=0;j<LB;j++)
lca_q[j][i]=0;
}
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
ed_num[i]=make_pair(a,b);
ed[a].push_back(b);
ed[b].push_back(a);
cost[a].push_back(c);
cost[b].push_back(c);
}
precompute(1);
HLD_init(1,1,0);
//cout<<counter<<"\n";
build_chain(1,1,counter-1);
for(int i=1;i<LB;i++)
{
for(int j=2;j<=n;j++)
{
lca_q[i][j]=lca_q[i-1][lca_q[i-1][j]];
}
}
while(1)
{
//fflush(stdin);
char str[100];
int a,b;
scanf("%s",str);
if(str[0]=='D')
break;
scanf("%d %d",&a,&b);
//cout<<str<<" "<<a<<" "<<b<<"\n";
if(str[0]=='Q')
{
a=HLD_query(a,b);
printf("%d\n",a);
}
if(str[0]=='C')
{
//if(ChainNum[a]==ChainNum[b])
up_use(b,a);
}
}
}
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIExCIDE1CnZlY3RvcjxpbnQ+IGVkWzExMDA3XSxjb3N0WzExMDA3XTsKcGFpcjxpbnQsaW50PiAgZWRfbnVtWzExMDA1XTsKaW50IHBvc0hMRFsxMTAwNV0sQ2hhaW5IZWFkWzExMDA1XT17MH0saGVpZ2h0WzExMDA0XSxsY2FfcVtMQl1bMTEwMDVdOy8vLE5vZGVOdW1bMTAwMDVdOwppbnQgQ2hhaW5OdW1bMTEwMDVdLGNvdW50ZXIsc3Vic2l6ZVsxMTAwNV0sc2VnWzYwMDA1XSxjaGFpbl9lZFsxMTAwNV0sQ2hhaW5ObzsKaW50IHByZWNvbXB1dGUoaW50IG5vZGUpCnsKICAgIGludCBhbnM9MTsKICAgIGZvcihpbnQgaT0wO2k8ZWRbbm9kZV0uc2l6ZSgpO2krKykKICAgIHsKICAgICAgICBpbnQgeD1lZFtub2RlXVtpXTsKICAgICAgICBpZihsY2FfcVswXVtub2RlXSE9eCkKICAgICAgICAgICB7CiAgICAgICAgICAgICAgIGxjYV9xWzBdW3hdPW5vZGU7CiAgICAgICAgICAgICAgIGFucys9cHJlY29tcHV0ZSh4KTsKICAgICAgICAgICB9CiAgICB9CiAgICBzdWJzaXplW25vZGVdPWFuczsKICAgIHJldHVybiBhbnM7Cn0KCnZvaWQgSExEX2luaXQoaW50IG5vZGUsaW50IGgsaW50IGNvc3RzKQp7CiAgIGludCBzcGVjaWFsX2NoaWxkPTAsbXg9MCxteGk9MCxteGlpOwogICBoZWlnaHRbbm9kZV09aDsKICAgaWYoIUNoYWluSGVhZFtDaGFpbk5vXSkKICAgICAgIHsKICAgICAgICAgICBDaGFpbkhlYWRbQ2hhaW5Ob109bm9kZTsKICAgICAgICAgICAvL2NvdW50ZXI9MTsKICAgICAgIH0KICAgcG9zSExEW25vZGVdPWNvdW50ZXI7CiAgIC8vTm9kZU51bVtjb3VudGVyXT1ub2RlOwogICAvL2NoYWluX3NpemVbQ2hhaW5Ob109Y291bnRlcjsKICAgY2hhaW5fZWRbY291bnRlcl09Y29zdHM7Ly9DaGlsZCBzaWRlIG9mIHRoZSBlZGdlIGtlZXBzIHRoZSBjb3N0IG9mIHRoZSBlZGdlCiAgIGNvdW50ZXIrKzsKICAgLy9jb3V0PDxjb3VudGVyPDwiXG4iOwogICBDaGFpbk51bVtub2RlXT1DaGFpbk5vOwoKICAgZm9yKGludCBpPTA7aTxlZFtub2RlXS5zaXplKCk7aSsrKQogICB7CiAgICAgICBpbnQgeD1lZFtub2RlXVtpXTsKICAgICAgIGlmKGxjYV9xWzBdW25vZGVdIT14KQogICAgICAgewogICAgICAgICAgIGlmKG14PHN1YnNpemVbeF0pCiAgICAgICAgICAgewogICAgICAgICAgICAgICBteD1zdWJzaXplW3hdOwogICAgICAgICAgICAgICBteGk9eDsKICAgICAgICAgICAgICAgbXhpaT1pOwogICAgICAgICAgIH0KICAgICAgIH0KICAgfQogICBzcGVjaWFsX2NoaWxkPW14aTsKICAgaWYoc3BlY2lhbF9jaGlsZCkKICAgICAgSExEX2luaXQoc3BlY2lhbF9jaGlsZCxoKzEsY29zdFtub2RlXVtteGlpXSk7CgogICBmb3IoaW50IGk9MDtpPGVkW25vZGVdLnNpemUoKTtpKyspCiAgIHsKICAgICAgIGludCB4PWVkW25vZGVdW2ldOwogICAgICAgaWYobGNhX3FbMF1bbm9kZV0hPXgmJnghPXNwZWNpYWxfY2hpbGQpCiAgICAgICB7CiAgICAgICAgICAgQ2hhaW5ObysrOwogICAgICAgICAgIC8vY29ubmVjdG9yW2NoYWluXVsoKmNoKV09Y29ubmVjdG9yWygqY2gpXVtjaGFpbl09Y29zdFtub2RlXVtpXTsKICAgICAgICAgICBITERfaW5pdCh4LGgrMSxjb3N0W25vZGVdW2ldKTsKICAgICAgIH0KICAgfQogICByZXR1cm47Cgp9CmludCBsY2FfdHJlZShpbnQgYSxpbnQgYikKewogICAgaW50IGhhLGhiLGRpZmY7CiAgICBpZihhPT1iKQogICAgICAgIHJldHVybiBhOwogICAgaWYoaGVpZ2h0W2FdPmhlaWdodFtiXSkKICAgIHsKICAgICAgICBhPWFeYjsKICAgICAgICBiPWFeYjsKICAgICAgICBhPWFeYjsKICAgIH0KICAgIGhhPWhlaWdodFthXSxiPWhlaWdodFtiXTsKICAgIGRpZmY9aGItaGE7CiAgICBmb3IoaW50IGk9MDtpPExCO2krKykKICAgICAgICBpZigoZGlmZj4+aSkmMSkKICAgICAgICAgIGE9bGNhX3FbaV1bYV07CiAgICBpZihhPT1iKXJldHVybiBhOwogICAgZm9yKGludCBpPUxCLTE7aT49MDtpLS0pCiAgICAgICAgaWYobGNhX3FbaV1bYV0hPWxjYV9xW2ldW2JdKQogICAgICAgewogICAgICAgICBhPWxjYV9xW2ldW2FdOwogICAgICAgICBiPWxjYV9xW2ldW2JdOwogICAgICAgfQogICAgcmV0dXJuIGxjYV9xWzBdW2FdOwp9CnZvaWQgYnVpbGRfY2hhaW4oaW50IG5vZGUsaW50IGwsaW50IHIpCnsKICAgIGlmKGw9PXIpCiAgICB7CiAgICAgICAgc2VnW25vZGVdPWNoYWluX2VkW3JdOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQ9KGwrcik+PjEsY2hpbGQ9bm9kZTw8MTsvLyxuMT1Ob2RlTnVtW21pZF0sbjI9Tm9kZU51bVttaWQrMV07CiAgICBidWlsZF9jaGFpbihjaGlsZCxsLG1pZCk7CiAgICBidWlsZF9jaGFpbihjaGlsZCsxLG1pZCsxLHIpOwogICAgc2VnW25vZGVdPW1heChzZWdbY2hpbGRdLHNlZ1tjaGlsZCsxXSk7CgogICAgLy9zZWdbY2hhaW5dW25vZGVdPW1heChzZWdbY2hhaW5dW25vZGVdLGNoYWluX2VkW2NoYWluXVttaWRdKTsKICAgIC8vY291dDw8bDw8IiAiPDxyPDwiXG4iOwogICAgLy9jb3V0PDxzZWdbbm9kZV08PCJcbiI7CgogICAgIHJldHVybjsKfQppbnQgcXVlcnkoaW50IG5vZGUsaW50IGwsaW50IHIsaW50IHFsLGludCBxcikKewoKICAgIGlmKHFsPD1sJiZyPD1xcikKICAgIHsKICAgICAgICByZXR1cm4gc2VnW25vZGVdOwogICAgfQogICAgaW50IG1pZD0obCtyKT4+MSxjaGlsZD1ub2RlPDwxLGFucz0wOy8vLG4xPU5vZGVOdW1bbWlkXSxuMj1Ob2RlTnVtW21pZCsxXTsKICAgIGlmKG1pZD49cWwpIGFucz1xdWVyeShjaGlsZCxsLG1pZCxxbCxxcik7CiAgICBpZihtaWQrMTw9cXIpIGFucz1tYXgoYW5zLHF1ZXJ5KGNoaWxkKzEsbWlkKzEscixxbCxxcikpOwogICAgLy9pZihtaWQ+PXFsJiZtaWQrMTw9cXIpCiAgICAgICAgLy9hbnM9bWF4KGFucyxjaGFpbl9lZFtjaGFpbl1bbWlkXSk7CiAgICByZXR1cm4gYW5zOwp9CnZvaWQgdXBkYXRlKGludCBub2RlLGludCBsLGludCByLGludCBhLGludCB2YWwpCnsKICAgIC8vaWYoKGw9PWEmJmw9PXIpfHwobD09YiYmbD09cikpCiAgICAgIC8vcmV0dXJuOwogICAgLy9pZihsKQogICAgLy9jb3V0PDxsPDwiICI8PHI8PCJcbiI7CiAgICAvL2dldGNoYXIoKTsKICAgIGlmKGw9PXIpCiAgICB7CiAgICAgICAgaWYobD09YSkKICAgICAgICB7CiAgICAgICAgICAgIGNoYWluX2VkW2xdPXZhbDsKICAgICAgICAgICAgc2VnW25vZGVdPXZhbDsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIDsKICAgIH0KICAgIGludCBtaWQ9KGwrcik+PjEsY2hpbGQ9bm9kZTw8MSxmbGFnPTA7CiAgICBpZihtaWQ+PWEpIHsKICAgICAgICAgICAgdXBkYXRlKGNoaWxkLGwsbWlkLGEsdmFsKTsKICAgICAgICAgICAgLy9mbGFnKys7CiAgICB9CiAgICBpZihtaWQrMTw9YSkgewogICAgICAgICAgICB1cGRhdGUoY2hpbGQrMSxtaWQrMSxyLGEsdmFsKTsKICAgICAgICAgICAgLy9mbGFnKys7CiAgICB9CiAgICBzZWdbbm9kZV09bWF4KHNlZ1tjaGlsZF0sc2VnW2NoaWxkKzFdKTsKICAgIC8vaWYoZmxhZz09MikKICAgIC8vewogICAgICAgIC8vY2hhaW5fZWRbY2hhaW5dW21pZF09dmFsOwogICAgICAgIC8vc2VnW2NoYWluXVtub2RlXT1tYXgoc2VnW2NoYWluXVtub2RlXSx2YWwpOwogICAgICAgIC8vcmV0dXJuOwogICAgLy99CiAgICByZXR1cm47Cn0KaW50IHN1Yl9xdWVyeShpbnQgdSxpbnQgdikKewogICAgaW50IHVjaGFpbj1DaGFpbk51bVt1XSx2Y2hhaW49Q2hhaW5OdW1bdl0sbXg9MDsKICAgIHdoaWxlKDEpCiAgICB7CiAgICAgICAgLy9jb3V0PDxwb3NITERbdV08PCIgIjw8cG9zSExEW3ZdPDwiXG4iOwogICAgICAgIGlmKHVjaGFpbj09dmNoYWluKQogICAgICAgIHsKICAgICAgICAgIGludCBhbnM9MDsKICAgICAgICAgIGlmKHUhPXYpCiAgICAgICAgICAgIGFucz1xdWVyeSgxLDEsY291bnRlci0xLHBvc0hMRFt2XSsxLHBvc0hMRFt1XSk7CiAgICAgICAgICBteD1tYXgobXgsYW5zKTsKICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgICAgICBpbnQgYW5zPXF1ZXJ5KDEsMSxjb3VudGVyLTEscG9zSExEW0NoYWluSGVhZFt1Y2hhaW5dXSxwb3NITERbdV0pOwogICAgICAgIGlmKGFucz5teCkKICAgICAgICAgICAgbXg9YW5zOwogICAgICAgIHU9Q2hhaW5IZWFkW3VjaGFpbl07CiAgICAgICAgdT1sY2FfcVswXVt1XTsKCiAgICAgICAgLy9teD1tYXgobXgsY29ubmVjdG9yW3VjaGFpbl1bdV0pOwogICAgICAgIHVjaGFpbj1DaGFpbk51bVt1XTsKICAgIH0KICAgIHJldHVybiBteDsKfQovL0xDQSBjYWxjdWxhdGlvbiByZW1haW5pbmcKaW50IEhMRF9xdWVyeShpbnQgYSxpbnQgYikKewogIGludCBsY2E9bGNhX3RyZWUoYSxiKTsKICAvL2NvdXQ8PGxjYTw8IlN1YiBRdWVyeVxuIjsKICByZXR1cm4gbWF4KHN1Yl9xdWVyeShhLGxjYSksc3ViX3F1ZXJ5KGIsbGNhKSk7Cn0KaW50IHVwX3VzZShpbnQgdmFsLGludCBudW0pCnsKICAgIGludCBhPWVkX251bVtudW1dLmZpcnN0LGI9ZWRfbnVtW251bV0uc2Vjb25kOwogICAgaWYoYT09bGNhX3FbMF1bYl0pCiAgICAgIHVwZGF0ZSgxLDEsY291bnRlci0xLHBvc0hMRFtiXSx2YWwpOwogICAgZWxzZSB1cGRhdGUoMSwxLGNvdW50ZXItMSxwb3NITERbYV0sdmFsKTsKCgp9CmludCBtYWluKCkKewogaW50IHQ7CiBzY2FuZigiJWRcbiIsJnQpOwogd2hpbGUodC0tKQogewogICAgIGludCBuOwogICAgIC8vZ2V0Y2hhcigpOwogICAgIHNjYW5mKCIlZCIsJm4pOwogICAgIGNvdW50ZXI9MSxDaGFpbk5vPTE7CiAgICAgZm9yKGludCBpPTE7aTxuO2krKykKICAgICB7CiAgICAgICAgIGVkW2ldLmNsZWFyKCk7CiAgICAgICAgIGNvc3RbaV0uY2xlYXIoKTsKICAgICAgICAgQ2hhaW5IZWFkW2ldPTA7CiAgICAgICAgIGZvcihpbnQgaj0wO2o8TEI7aisrKQogICAgICAgICAgICBsY2FfcVtqXVtpXT0wOwogICAgIH0KICAgICBmb3IoaW50IGk9MTtpPG47aSsrKQogICAgIHsKICAgICAgICAgaW50IGEsYixjOwogICAgICAgICBzY2FuZigiJWQgJWQgJWQiLCZhLCZiLCZjKTsKICAgICAgICAgZWRfbnVtW2ldPW1ha2VfcGFpcihhLGIpOwogICAgICAgICBlZFthXS5wdXNoX2JhY2soYik7CiAgICAgICAgIGVkW2JdLnB1c2hfYmFjayhhKTsKICAgICAgICAgY29zdFthXS5wdXNoX2JhY2soYyk7CiAgICAgICAgIGNvc3RbYl0ucHVzaF9iYWNrKGMpOwogICAgIH0KICAgICBwcmVjb21wdXRlKDEpOwoKICAgICBITERfaW5pdCgxLDEsMCk7CiAgICAgLy9jb3V0PDxjb3VudGVyPDwiXG4iOwogICAgIGJ1aWxkX2NoYWluKDEsMSxjb3VudGVyLTEpOwogICAgIGZvcihpbnQgaT0xO2k8TEI7aSsrKQogICAgIHsKICAgICAgICAgZm9yKGludCBqPTI7ajw9bjtqKyspCiAgICAgICAgIHsKICAgICAgICAgICAgIGxjYV9xW2ldW2pdPWxjYV9xW2ktMV1bbGNhX3FbaS0xXVtqXV07CiAgICAgICAgIH0KICAgICB9CiAgICAgd2hpbGUoMSkKICAgICB7CiAgICAgICAgIC8vZmZsdXNoKHN0ZGluKTsKICAgICAgICAgY2hhciBzdHJbMTAwXTsKICAgICAgICAgaW50IGEsYjsKICAgICAgICAgc2NhbmYoIiVzIixzdHIpOwogICAgICAgICBpZihzdHJbMF09PSdEJykKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgIHNjYW5mKCIlZCAlZCIsJmEsJmIpOwogICAgICAgICAvL2NvdXQ8PHN0cjw8IiAiPDxhPDwiICI8PGI8PCJcbiI7CiAgICAgICAgIGlmKHN0clswXT09J1EnKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBhPUhMRF9xdWVyeShhLGIpOwogICAgICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixhKTsKICAgICAgICAgICAgfQogICAgICAgIGlmKHN0clswXT09J0MnKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL2lmKENoYWluTnVtW2FdPT1DaGFpbk51bVtiXSkKICAgICAgICAgICAgICAgIHVwX3VzZShiLGEpOwogICAgICAgICAgICB9CgogICAgIH0KIH0KfQo=