题意:给定一棵树,告诉了每条边的权值,然后给出两种操作:
(1)把第i条边的权值改为val
(2)询问a,b路径上权值最大的边
小心x==y的时候特判下
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
const int oo=10000010;
struct node{
int w,u,v,next;
}a[40010];
int siz[20010],son[20010],begin[20010];
int deep[20010],top[20010],fa[20010];
int tot,b[20010],bh[20010];
/*void swap(int *x,int *y){
int t=*x;
*x=*y;*y=t;
return;
}*/
int max(int x,int y){
if(x>y)return x;
else return y;
}
void add(int x,int y,int w){
a[++tot].v=y;
a[tot].u=x;
a[tot].w=w;
a[tot].next=begin[x];
begin[x]=tot;
return;
}
void dfs1(int u,int father,int d){
fa[u]=father;
deep[u]=d;
siz[u]=1;
int h=begin[u];
while(h){
if(a[h].v!=father){
dfs1(a[h].v,u,d+1);
siz[u]+=siz[a[h].v];
if(siz[a[h].v]>siz[son[u]])
son[u]=a[h].v;
}
h=a[h].next;
}
return;
}
void dfs2(int u,int tp){
top[u]=tp;
bh[u]=++tot;
if(son[u]==0)
return;
dfs2(son[u],tp);
int h=begin[u];
while(h){
if(a[h].v!=fa[u] && a[h].v!=son[u])
dfs2(a[h].v,a[h].v);
h=a[h].next;
}
return;
}
//线段树部分
struct node1{
int l,r,max;
}tree[100010];
int home(int l,int r,int d){
if(l==r){
tree[d].l=l;
tree[d].r=r;
tree[d].max=b[l];
return b[l];
}
tree[d].l=l;
tree[d].r=r;
int mid=(l+r)>>1;
int x1=home(l,mid,d<<1);
int x2=home(mid+1,r,d<<1|1);
tree[d].max=max(x1,x2);
return tree[d].max;
}
int change(int d,int x,int y){
if(tree[d].l==tree[d].r){
tree[d].max=y;
return y;
}
int mid=(tree[d].l+tree[d].r)>>1;
if(x<=mid)
change(d<<1,x,y);
else
change(d<<1|1,x,y);
tree[d].max=max(tree[d<<1].max,tree[d<<1|1].max);
return tree[d].max;
}
int find(int d,int l,int r){
if(l<=tree[d].l && r>=tree[d].r)
return tree[d].max;
int mid=(tree[d].l+tree[d].r)>>1;
int x1=-oo,x2=-oo;
if(l<=mid)
x1=find(d<<1,l,r);
if(r>mid)
x2=find(d<<1|1,l,r);
return max(x1,x2);
}
int query(int x,int y){
int ans=-oo;
while(top[x]!=top[y]){
if(deep[top[y]]>deep[top[x]])
std::swap(x,y);
ans=max(ans,find(1,bh[top[x]],bh[x]));
x=fa[top[x]];
}
if(deep[x]>deep[y])
std::swap(x,y);
if(x==y)return ans;
ans=max(ans,find(1,bh[x]+1,bh[y]));
return ans;
}
int mmp=0;
int main(){
int t,i,n,x,y,w,c;
char cc[20];
scanf("%d",&t);
while(t--){
for(i=1;i<=10001;i++){
siz[i]=0;son[i]=0;begin[i]=0;
}
tot=0;
scanf("%d",&n);
for(i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
int tot1=tot;
tot=0;
dfs1(1,1,1);
tot=0;
dfs2(1,1);
for(i=1;i<=tot1;i++){
if(deep[a[i].u]>deep[a[i].v])
b[bh[a[i].u]]=a[i].w;
else
b[bh[a[i].v]]=a[i].w;
}
home(2,n,1);
while(1){
scanf("%s",cc);
if(cc[0]=='D')
break;
scanf("%d%d",&x,&y);
if(cc[0]=='Q'){
if(x==y)printf("0\n");
else printf("%d\n",query(x,y));
}
else{
if(deep[a[x<<1].u]>deep[a[x<<1].v])
change(1,bh[a[x<<1].u],y);
else
change(1,bh[a[x<<1].v],y);
}
}
}
return 0;
}