思路
注意本题只能用C，不能用C++
其他的都和上一题一样
代码
#include <stdio.h>
#include <string.h>
#define MAXN 10010
int dfs_clock,dep[MAXN*2],heason[MAXN*2],id[MAXN*2],sz[MAXN*2],top[MAXN*2],fa[MAXN*2],w_p[MAXN*2],v[MAXN*2],fir[MAXN*2],nxt[MAXN*2],w[MAXN*2],val[MAXN*2],maxx[MAXN*5],cnt;
struct Edge{
int u,v,w;
}E[MAXN*2];
int max(int a,int b){
return (a>b)?a:b;
}
void addedge(int ui,int vi,int wi){
++cnt;
v[cnt]=vi;
w[cnt]=wi;
nxt[cnt]=fir[ui];
fir[ui]=cnt;
}
void dfs1(int u,int f,int wx){
fa[u]=f;
sz[u]=1;
w_p[u]=wx;
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f)
continue;
dep[v[i]]=dep[u]+1;
dfs1(v[i],u,w[i]);
sz[u]+=sz[v[i]];
if(heason[u]==0||sz[v[i]]>sz[heason[u]])
heason[u]=v[i];
}
}
void dfs2(int u,int f,int topf){
id[u]=++dfs_clock;
val[id[u]]=w_p[u];
top[u]=topf;
if(!heason[u])
return;
dfs2(heason[u],u,topf);
for(int i=fir[u];i;i=nxt[i]){
if(v[i]==f||v[i]==heason[u])
continue;
dfs2(v[i],u,v[i]);
}
}
void pushup(int o){
maxx[o]=max(maxx[o<<1],maxx[o<<1|1]);
}
void build(int l,int r,int o){
if(l==r){
maxx[o]=val[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,o<<1);
build(mid+1,r,o<<1|1);
pushup(o);
}
void update1(int l,int r,int pos,int o,int c){
if(l==r){
maxx[o]=c;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)
update1(l,mid,pos,o<<1,c);
else
update1(mid+1,r,pos,o<<1|1,c);
pushup(o);
}
void update(int o,int c){
update1(1,dfs_clock,id[o],1,c);
}
int query1(int L,int R,int l,int r,int o){
if(L<=l&&r<=R)
return maxx[o];
int mid=(l+r)>>1,ans=0;
if(L<=mid)
ans=max(ans,query1(L,R,l,mid,o<<1));
if(R>mid)
ans=max(ans,query1(L,R,mid+1,r,o<<1|1));
return ans;
}
int query(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
int t=x;
x=y;
y=t;
}
ans=max(ans,query1(id[top[x]],id[x],1,dfs_clock,1));
x=fa[top[x]];
}
if(dep[x]>dep[y]){
int t=x;
x=y;
y=t;
}
ans=max(ans,query1(id[x],id[y],1,dfs_clock,1));
return ans;
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
int t=x;
x=y;
y=t;
}
x=fa[top[x]];
}
return (dep[x]<dep[y])?x:y;
}
void init(void){
dfs_clock=0;
memset(dep,0,sizeof(dep));
memset(heason,0,sizeof(heason));
memset(id,0,sizeof(id));
memset(sz,0,sizeof(sz));
memset(top,0,sizeof(top));
memset(fa,0,sizeof(fa));
memset(w_p,0,sizeof(w_p));
memset(v,0,sizeof(v));
memset(fir,0,sizeof(fir));
memset(nxt,0,sizeof(nxt));
memset(w,0,sizeof(w));
memset(val,0,sizeof(val));
memset(maxx,0,sizeof(maxx));
cnt=0;
memset(E,0,sizeof(E));
}
int n,T;
int main(){
scanf("%d",&T);
while(T--){
init();
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].w);
addedge(E[i].u,E[i].v,E[i].w);
addedge(E[i].v,E[i].u,E[i].w);
}
dfs1(1,0,0);
dfs2(1,0,1);
build(1,dfs_clock,1);
char opt[10];
while(1){
scanf("%s",&opt);
if(opt[0]=='D')
break;
if(opt[0]=='Q'){
int a,b;
scanf("%d %d",&a,&b);
int LCA=lca(a,b);
// printf("lca=%d\n",LCA);
int t=w_p[LCA];
update(LCA,0);
int ans=query(a,b);
update(LCA,t);
printf("%d\n",ans);
}
else{
int a,b;
scanf("%d %d",&a,&b);
int t=(dep[E[a].u]>dep[E[a].v])?E[a].u:E[a].v;
w_p[t]=b;
update(t,b);
}
}
}
return 0;
}