n个点q个查询开始位置s
n-1条边 a b c a b之间有一条边 权值为c
q个查询 0 a 输出现在的位置到 a 所需时间
1 a b 更新第a条边的权为b
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 100010 struct edge { int from,to,w,next; }x[MAXN<<1],s1[MAXN]; int head[MAXN],siz[MAXN],father[MAXN],dep[MAXN],top[MAXN],intree[MAXN],outtree[MAXN],son[MAXN],val[MAXN]; int cnt,tim,n; void add(int u,int v,int w) { x[cnt].from=u; x[cnt].to=v; x[cnt].w=w; x[cnt].next=head[u]; head[u]=cnt++; } void dfs1(int u,int fa) { siz[u]=1; father[u]=fa; dep[u]=dep[fa]+1; for(int i=head[u];i!=-1;i=x[i].next) { int v=x[i].to; if(v==fa) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int tp) { top[u]=tp; intree[u]=++tim; outtree[tim]=u; if(son[u]!=0) dfs2(son[u],tp); for(int i=head[u];i!=-1;i=x[i].next) { int v=x[i].to; if(v==son[u]||v==father[u]) continue; dfs2(v,v); } } struct node { int l,r,w; }z[MAXN<<3]; void Build(int l,int r,int a) { z[a].l=l; z[a].r=r; if(l==r) { z[a].w=val[l]; return ; } int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); z[a].w=z[a<<1].w+z[a<<1|1].w; } void update(int l,int r,int a1,int w,int a)//单点更新 { if(l==r) { z[a].w=w; return ; } int mid=(l+r)>>1; if(a1<=mid) update(l,mid,a1,w,a<<1); else update(mid+1,r,a1,w,a<<1|1); z[a].w=z[a<<1].w+z[a<<1|1].w; } int ques(int l,int r,int a1,int b1,int a)//区间求和 { int ans=0; if(a1<=l&&r<=b1) return z[a].w; int mid=(l+r)>>1; if(a1<=mid) ans+=ques(l,mid,a1,b1,a<<1); if(b1>mid) ans+=ques(mid+1,r,a1,b1,a<<1|1); return ans; } int change(int x,int y) { int ans=0; while(top[x] != top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=ques(1,n,intree[top[x]],intree[x],1); x=father[top[x]]; } if(x==y) return ans; if(dep[x] > dep[y]) swap(x,y); ans+=ques(1,n,intree[x]+1,intree[y],1);//这边左边的是要加1的 return ans; } int main() { int q,s; while(scanf("%d%d%d",&n,&q,&s)!=EOF) { memset(head,-1,sizeof(head)); memset(son,0,sizeof(son)); cnt=1; tim=0; for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&s1[i].from,&s1[i].to,&s1[i].w);//存到另外一个数组里 add(s1[i].from,s1[i].to,s1[i].w); add(s1[i].to,s1[i].from,s1[i].w); } dfs1(1,0); dfs2(1,1); for(int i=1;i<n;i++) //边的权放到点上 那么只要区间求和就可以了 其实里面还有问题 { if(dep[s1[i].from]<dep[s1[i].to]) swap(s1[i].from,s1[i].to); val[intree[s1[i].from]]=s1[i].w; } Build(1,n,1); while(q--) { int a; scanf("%d",&a); if(a==0) { int b; scanf("%d",&b); printf("%d ",change(s,b)); s=b; } else { int b,c; scanf("%d%d",&b,&c); update(1,n,intree[s1[b].from],c,1); } } } return 0; }