[ exttt{Preface}
]
这题在 ( ext{Luogu}) 上竟然不能交 (C++) ，会一直 (Waiting) ，只能交非 (C++) 的语言。
所以打完了 (C++) 要转到 (C) 才能过。
要把什么 (swap) ， (max) 各种函数换成手写，以及 (C++) 的特色（例如 using namespace std; 和 inline ）都要去掉。
详情见 (Code) 。
[ exttt{Description}
]
给出一个 (n) 个点的带权树，需要支持以下操作：
CHANGE i ti将第 (i) 条边的权值改为 (t_i) 。QUERY a b询问 (a) 到 (b) 的路径上最大边权。
多组数据。
[ exttt{Solution}
]
从这个询问 " 查询路径信息，边带修 " 来说，我们可以知道这是一个树剖板子题。
不了解树剖的童鞋可以去了解一下，过一下 树剖模板 。
只不过这题不是一般的 " 点带修 " 而是 " 边带修 " ，也不要紧。
注意到除了根，每个节点都有父亲，那么我们可以把边的信息转化到点身上，每个节点的点权是它与它父亲所形成的边的边权。
例如 (1) 到 (2) 的一条长度为 (3) 的边（此时 (1) 是 (2) 的父亲），那么我们可以理解为 (2) 的点权是 (3) 。
这样就可以用树剖维护了。
但是令 (z= ext{lca}(x,y)) ，我们发现 ((fa[z],z)) 这条边是不能被算进答案的。
在查询的最后一步，(x) 和 (y) 会在同一条重链上（设 (dep_x<dep_y)），此时 (x) 就是 (z) ，由于重链上的节点的 (dfs) 序是连续的，所以查询 ([dfn_x+1,dfn_y]) 这段区间的最大值就可以避开计算 (z) 的信息了。
[ exttt{Code}
]
#include<stdio.h>
#define N 10100
#define M 20100
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
int tmp;
int max(int a,int b){return a>b?a:b;}
int T;
int n;
struct Edge{
int u,v,w;
}e[N];
int tot,head[N],ver[M],edge[M],Next[M];
void add(int u,int v,int w)
{
ver[++tot]=v; edge[tot]=w; Next[tot]=head[u]; head[u]=tot;
}
int val[N];
int d[N];
int fu[N];
int size[N];
int son[N];
void dfs1(int u)
{
size[u]=1;
for(int i=head[u];i;i=Next[i])
{
int v=ver[i],w=edge[i];
if(v==fu[u])continue;
fu[v]=u;
val[v]=w;
d[v]=d[u]+1;
dfs1(v);
size[u]+=size[v];
if(size[son[u]]<size[v])son[u]=v;
}
}
int QwQ;
int dfn[N],idx[N];
int top[N];
void dfs2(int u)
{
QwQ++;
dfn[u]=QwQ,idx[QwQ]=u;
if(son[u])
{
top[son[u]]=top[u];
dfs2(son[u]);
}
for(int i=head[u];i;i=Next[i])
{
int v=ver[i];
if(v==fu[u]||v==son[u])continue;
top[v]=v;
dfs2(v);
}
}
struct SegmentTree{
int l,r;
int max;
}t[N*4];
void upd(int p)
{
t[p].max=max(t[p*2].max,t[p*2+1].max);
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r)
{
t[p].max=val[idx[l]];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
upd(p);
}
void change(int p,int delta,int val)
{
if(t[p].l==t[p].r)
{
t[p].max=val;
return;
}
int mid=(t[p].l+t[p].r)/2;
if(delta<=mid)
change(p*2,delta,val);
else
change(p*2+1,delta,val);
upd(p);
}
int ask(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r)return t[p].max;
int mid=(t[p].l+t[p].r)/2;
int val=0;
if(l<=mid)
val=max(val,ask(p*2,l,r));
if(mid<r)
val=max(val,ask(p*2+1,l,r));
return val;
}
int path_ask(int u,int v)
{
int ans=0;
while(top[u]!=top[v])
{
if(d[top[u]]>d[top[v]])tmp=u,u=v,v=tmp;
ans=max(ans,ask(1,dfn[top[v]],dfn[v]));
v=fu[top[v]];
}
if(u==v)return ans;
if(d[u]>d[v])tmp=u,u=v,v=tmp;
ans=max(ans,ask(1,dfn[u]+1,dfn[v]));
return ans;
}
void work()
{
tot=QwQ=0;
for(int i=1;i<=n;i++)
head[i]=son[i]=0;
n=read();
for(int i=1;i<n;i++)
{
e[i].u=read(),e[i].v=read(),e[i].w=read();
add(e[i].u,e[i].v,e[i].w),add(e[i].v,e[i].u,e[i].w);
}
d[1]=1,top[1]=1;
dfs1(1),dfs2(1);
build(1,1,n);
char opt[10];
while(scanf("%s",opt),opt[0]!='D')
{
int x=read(),y=read();
switch(opt[0])
{
case 'C':{
if(d[e[x].u]>d[e[x].v])
tmp=e[x].u,e[x].u=e[x].v,e[x].v=tmp;
change(1,dfn[e[x].v],y);
break;
}
case 'Q':{
printf("%d
",path_ask(x,y));
break;
}
}
}
}
int main()
{
T=read();
while(T--) work();
return 0;
}
[ exttt{Thanks} exttt{for} exttt{watching}
]