【题目翻译】
给定 (n) 个点的树，边按输入顺序编号为 (1,2, ldots, n-1)，要求作以下操作：
CHANGE i ti将第 (i) 条边权值改为 (t_i)；QUERY a b询问从 (a) 点到 (b) 点路径上的最大边权。
有多组测试数据，每组数据以 DONE 结尾。
【样例输入】
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【样例输出】
1
3
【数据规模与约定】
数据组数 (le 20)，(n leq10^4)，边权 (le 10^6)。
其实就是树链剖分的板子题。。。
树剖板子 ( o) 这里
因为给的是边权，所以我们要将边权转化成点权，我们可以将边权传给这条边所连的深度较深的点上。
由于我们把边权传给了深度较深的点，所以对于 (operatorname{LCA}(x,y)) 是不能算在路径上的。
在板子上加几句话就好了
int qask(int x,int y){
if(x==y) return 0;//如果两个点相同直接返回0
int maxx=-INT_MAX;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
maxx=max(maxx,ask_Max(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(x==y) return maxx;//如果x或y是lca直接退出
if(dep[x]<dep[y]) swap(x,y);
maxx=max(maxx,ask_Max(1,1,n,id[y]+1,id[x]));//y是lca，所以从id[y]+1开始查询
return maxx;
}
完整代码如下：
#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline int read(){
int s=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
return f?s:-s;
}
struct Edge{
int x,y,v;
}G[10010];
int n,val[10010],Max[40010];
int tot,head[10010],ver[20010],nxt[20010],edge[20010];
int Size[10010],dep[10010],son[10010],fa[10010];
int cnt,top[10010],id[10010],bi[10010];
char s[11];
void add(int x,int y,int v){
nxt[++tot]=head[x]; ver[tot]=y;
head[x]=tot; edge[tot]=v;
}
void dfs_first(int x,int _fa){
Size[x]=1;
for(rint i=head[x];i;i=nxt[i]){
int y=ver[i],v=edge[i];
if(y==_fa) continue;
fa[y]=x; val[y]=v;
dep[y]=dep[x]+1;
dfs_first(y,x);
Size[x]+=Size[y];
if(Size[y]>Size[son[x]]) son[x]=y;
}
}
void dfs_second(int x,int top_point){
id[x]=++cnt; top[x]=top_point; bi[cnt]=x;
if(!son[x]) return;
dfs_second(son[x],top_point);
for(rint i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa[x]||y==son[x]) continue;
dfs_second(y,y);
}
}
void build(int p,int l,int r){
if(l==r) return Max[p]=val[bi[l]],void();
int mid=l+r>>1,lp=p<<1,rp=p<<1|1;
build(lp,l,mid); build(rp,mid+1,r);
Max[p]=max(Max[lp],Max[rp]);
}
void change(int p,int l,int r,int x,int v){
if(l==r) return Max[p]=v,void();
int mid=l+r>>1,lp=p<<1,rp=p<<1|1;
if(x<=mid) change(lp,l,mid,x,v);
else change(rp,mid+1,r,x,v);
Max[p]=max(Max[lp],Max[rp]);
}
int ask_Max(int p,int l,int r,int x,int y){
if(l>=x&&r<=y) return Max[p];
int mid=l+r>>1,lp=p<<1,rp=p<<1|1,maxx=-INT_MAX;
if(x<=mid) maxx=max(maxx,ask_Max(lp,l,mid,x,y));
if(y>mid) maxx=max(maxx,ask_Max(rp,mid+1,r,x,y));
return maxx;
}
int qask(int x,int y){
if(x==y) return 0;
int maxx=-INT_MAX;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
maxx=max(maxx,ask_Max(1,1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(x==y) return maxx;
if(dep[x]<dep[y]) swap(x,y);
maxx=max(maxx,ask_Max(1,1,n,id[y]+1,id[x]));
return maxx;
}
int main(){
int T=read();
while(T--){
memset(head,0,sizeof head);
memset(Size,0,sizeof Size);
memset(son,0,sizeof son);
n=read(); tot=0; cnt=0;
for(rint i=1;i<n;++i){
G[i].x=read(); G[i].y=read(); G[i].v=read();
add(G[i].x,G[i].y,G[i].v);
add(G[i].y,G[i].x,G[i].v);
}
dep[1]=1; dfs_first(1,0);
dfs_second(1,1);
build(1,1,n);
scanf("%s",s);
while(s[0]!='D'){
if(s[0]=='Q'){
int x=read(),y=read();
printf("%d
",qask(x,y));
}
if(s[0]=='C'){
int i=read(),v=read(),x=G[i].x,y=G[i].y;
if(fa[x]==y) swap(x,y);
change(1,1,n,id[y],v);
}
scanf("%s",s);
}
}
return 0;
}