参考ACdream的
用深度较深的点表示边 故build过程为(1,2,n)
关于修改的关系
注解里还有些待解决的和深入理解的地方
#include <bits/stdc++.h> #define N 10100 #define FREI freopen("in.txt","r",stdin) #define Mem(a,b) memset(a,b,sizeof(a)) #define lson root<<1 #define rson root<<1|1 #define Mid int mid=(l+r)>>1 #define inf 0x3f3f3f3f using namespace std; int n,m,k,siz[N],fa[N],son[N],cnt,f[N],invf[N],dep[N],tp[N],sum[N<<2],ans,ecnt; int wedge[N]; struct edge{ int v,cost,next; }; edge e[N<<2]; struct E{ int u,v,cost; }; E edg[N]; int head[N]; void add(int u,int v,int cost){ e[ecnt]=(edge){v,cost,head[u]}; head[u]=ecnt++; } void dfs1(int u,int father){ dep[u]=dep[father]+1; fa[u]=father; siz[u]++; for(int i=head[u];~i;i=e[i].next){//auto 有问题？？ int v=e[i].v; if(v!=father){ dfs1(v,u); siz[u]+=siz[v]; if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v; } } } void dfs2(int u,int top){ tp[u]=top; f[u]=++cnt;//时间戳 映射 invf[f[u]]=u;//逆映射 if(son[u]==-1)//忘了判断条件 return ; dfs2(son[u],top); for(int i=head[u];~i;i=e[i].next){ int v=e[i].v; if(v!=son[u]&&v!=fa[u]){ dfs2(v,v); } } } void push_up(int root,int l,int r){ sum[root]=max(sum[lson],sum[rson]); } void build(int root,int l,int r){ if(l==r){ sum[root]=wedge[l]; return ; } Mid; build(lson,l,mid); build(rson,mid+1,r); push_up(root,l,r); } void update(int root,int l,int r,int ql,int qr,int val){ if(l>qr||r<ql) return; if(l>=ql&&r<=qr){ sum[root]=val; return ; } Mid; update(lson,l,mid,ql,qr,val); update(rson,mid+1,r,ql,qr,val); push_up(root,l,r); } void query(int root,int l,int r,int ql,int qr){ if(l>qr||r<ql) return; if(l>=ql&&r<=qr){ ans=max(ans,sum[root]); return ; } Mid; query(lson,l,mid,ql,qr); query(rson,mid+1,r,ql,qr); } void change(int x,int y){ while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]]) swap(x,y); query(1,2,n,f[tp[x]],f[x]);//可以加上顶端上面的那条边！！ x=fa[tp[x]]; } if(dep[x]>dep[y]) swap(x,y); if(x!=y) query(1,2,n,f[x]+1,f[y]); } int main() { //FREI; int cas; for(scanf("%d",&cas);cas--;){ Mem(head,-1); Mem(dep,0); Mem(siz,0); Mem(son,-1); ecnt=cnt=0; scanf("%d",&n); for(int i=1;i<n;i++){ int u,v,c; scanf("%d%d%d",&u,&v,&c); edg[i].u=u,edg[i].v=v,edg[i].cost=c; add(u,v,c); add(v,u,c); } dfs1(1,1);// 0 1有区别？？？？？ dfs2(1,1); for(int i=1;i<n;i++){ int u=edg[i].u,v=edg[i].v,c=edg[i].cost; dep[u]>dep[v]?wedge[f[u]]=c:wedge[f[v]]=c; } build(1,2,n); char s[10]; getchar(); while(1){ scanf("%s",s); if(s[0]=='Q'){ int x,y; scanf("%d%d",&x,&y); ans=-inf; change(x,y); printf("%d\n",ans); } else if(s[0]=='C'){ int x,y; scanf("%d%d",&x,&y); int u=edg[x].u,v=edg[x].v; int id=dep[u]>dep[v]?f[u]:f[v]; update(1,2,n,id,id,y); } else break; } } }