自己写的比原来的板子常数小了不少嘻嘻，边权处理起来比点权要复杂一下
由于根节点没有被映射的边，其被访问到的顺序是0，直接排除在线段树外
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 100005 struct Edge{ int to,next; }edge[maxn<<1]; int head[maxn],tot,e[maxn][3]; int fa[maxn],son[maxn],num[maxn],deep[maxn]; int top[maxn],p[maxn],fp[maxn],pos; inline void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs1(int u,int pre,int dep){ fa[u]=pre;deep[u]=dep;num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==pre) continue; dfs1(v,u,dep+1); num[u]+=num[v]; if(son[u]==-1 || num[son[u]]<num[v]) son[u]=v; } } void getpos(int u,int sp){ top[u]=sp;p[u]=pos++;fp[p[u]]=u; if(son[u]==-1) return; getpos(son[u],sp); for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[u] || v==son[u]) continue; getpos(v,v); } } #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[maxn<<2]; inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];} void update(int pos,int val,int l,int r,int rt){ if(l==r) {sum[rt]=val;return;} int m=l+r>>1; if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r) return sum[rt]; int m=l+r>>1,res=0; if(L<=m) res+=query(L,R,lson); if(R>m) res+=query(L,R,rson); return res; } int query2(int u,int v){ int f1=top[u],f2=top[v],res=0; while(f1!=f2){ if(deep[f1]<deep[f2]) swap(f1,f2),swap(u,v); res+=query(p[f1],p[u],1,pos,1); u=fa[f1],f1=top[u]; } if(u==v) return res; if(deep[u]>deep[v]) swap(u,v); res+=query(p[son[u]],p[v],1,pos,1); return res; } void init(){ tot=pos=0; memset(head,-1,sizeof head); memset(son,-1,sizeof head); memset(sum,0,sizeof sum); } int main(){ int n,q,now,op,a,b; while(scanf("%d%d%d",&n,&q,&now)!=EOF){ init(); for(int i=1;i<n;i++){ scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]); addedge(e[i][0],e[i][1]);addedge(e[i][1],e[i][0]); } dfs1(1,0,0);getpos(1,1); for(int i=1;i<n;i++){ if(deep[e[i][0]]>deep[e[i][1]]) swap(e[i][0],e[i][1]); update(p[e[i][1]],e[i][2],1,pos,1); } while(q--){ scanf("%d",&op); if(op==0) {scanf("%d",&a);printf("%d ",query2(now,a));now=a;} else {scanf("%d%d",&a,&b);update(p[e[a][1]],b,1,pos,1);}//第a条边改为b } } return 0; }