树链剖分学习笔记
这里就不写具体实现了...只是为刚看懂什么是树链剖分的同学提供习题
其实树剖部分都差不多的，关键是线段树
可以把这里面5题A了大概就可以熟悉树链剖分了...
T1:LuoguP3384 【模板】树链剖分
都说了是模板，那就是模板咯...
考虑线段树实现 区间加、区间和，又是线段树模板...
树剖跳的时候，因为要更新子树，然后这里更新的话直接idx[x]+sz[x]-1就可以了（因为这些编号是相连的）
取模不要漏！！！
1 // luogu-judger-enable-o2 2 #include<cstdio> 3 #include<queue> 4 #include<iostream> 5 #include<cstring> 6 #define int long long 7 using namespace std; 8 inline int read(){ 9 int ans=0,f=1;char chr=getchar(); 10 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 11 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 12 return ans*f; 13 }const int M=300005; 14 int n,m,head[M<<1],ver[M<<1],nxt[M<<1],tot,son[M],dep[M],sz[M],idx[M],fa[M],tp[M],root,ha,a[M],b[M],sum[M<<2],lz[M<<2],rk[M]; 15 inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;} 16 void dfs1(int x,int f){ 17 sz[x]=1,fa[x]=f,dep[x]=dep[f]+1; 18 for(int i=head[x];i;i=nxt[i]){ 19 if(ver[i]==f) continue; 20 dfs1(ver[i],x); 21 sz[x]+=sz[ver[i]]; 22 if(sz[ver[i]]>sz[son[x]]) son[x]=ver[i]; 23 } 24 }int t; 25 void dfs2(int x,int topf){ 26 tp[x]=topf;idx[x]=++t;a[t]=b[x];rk[t]=x; 27 if(!son[x]) return; 28 dfs2(son[x],topf); 29 for(int i=head[x];i;i=nxt[i]) 30 if(!idx[ver[i]]) dfs2(ver[i],ver[i]); 31 } 32 #define ls (i<<1) 33 #define rs (i<<1|1) 34 #define mid ((l+r)>>1) 35 inline void Push_Up(int i){sum[i]=(sum[ls]+sum[rs]+ha)%ha;} 36 inline void Push_Down(int i,int l,int r){ 37 if(!lz[i]) return; 38 sum[ls]=(sum[ls]+lz[i]*(mid-l+1)%ha)%ha,sum[rs]=(sum[rs]+lz[i]*(r-mid)%ha)%ha; 39 lz[ls]=(lz[ls]+lz[i])%ha,lz[rs]=(lz[rs]+lz[i])%ha,lz[i]=0; 40 } 41 void Build(int i,int l,int r){ 42 if(l==r){sum[i]=a[l];return;} 43 Build(ls,l,mid),Build(rs,mid+1,r); 44 Push_Up(i); 45 } 46 void Update(int i,int l,int r,int ql,int qr,int z){ 47 if(ql<=l&&r<=qr){sum[i]=((r-l+1)*z+sum[i])%ha;lz[i]=(lz[i]+z)%ha;return;} 48 Push_Down(i,l,r); 49 if(ql<=mid) Update(ls,l,mid,ql,qr,z); 50 if(qr>mid) Update(rs,mid+1,r,ql,qr,z); 51 Push_Up(i); 52 } 53 int Query(int i,int l,int r,int ql,int qr){ 54 if(ql<=l&&r<=qr) return sum[i]; 55 Push_Down(i,l,r);int s=0; 56 if(ql<=mid) s=(s+Query(ls,l,mid,ql,qr))%ha; 57 if(qr>mid) s=(s+Query(rs,mid+1,r,ql,qr))%ha; 58 Push_Up(i); 59 return s; 60 } 61 void Query_1(int x,int y,int val){ 62 while(tp[x]!=tp[y]){ 63 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 64 Update(1,1,n,idx[tp[x]],idx[x],val); 65 x=fa[tp[x]]; 66 } 67 if(dep[x]>dep[y]) swap(x,y); 68 Update(1,1,n,idx[x],idx[y],val); 69 } 70 void Query_2(int x,int y){ 71 int Ans=0; 72 while(tp[x]!=tp[y]){ 73 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 74 Ans=(Ans+Query(1,1,n,idx[tp[x]],idx[x]))%ha; 75 x=fa[tp[x]]; 76 }if(dep[x]>dep[y]) swap(x,y); 77 Ans=(Ans+Query(1,1,n,idx[x],idx[y]))%ha; 78 printf("%lld\n",Ans); 79 } 80 void Query_3(int x,int y){Update(1,1,n,idx[x],idx[x]+sz[x]-1,y%ha);} 81 void Query_4(int x){printf("%lld\n",Query(1,1,n,idx[x],idx[x]+sz[x]-1));} 82 int Q_d(int i,int l,int r,int p){ 83 if(l==r)return sum[i]; 84 Push_Up(i); 85 if(p<=mid) return Q_d(ls,l,mid,p); 86 else return Q_d(rs,mid+1,r,p); 87 } 88 signed main(){ 89 n=read(),m=read(),root=read(),ha=read(); 90 for(int i=1;i<=n;++i) b[i]=read(); 91 for(int i=1,x,y,z;i<n;++i){x=read(),y=read(),add(x,y),add(y,x);} 92 dfs1(root,0),dfs2(root,root),Build(1,1,n); 93 while(m--){int opt=read(),x,y,z; 94 if(opt==4) x=read(),Query_4(x); 95 else{x=read(),y=read(); 96 if(opt==3) Query_3(x,y%ha); 97 else if(opt==2) Query_2(x,y); 98 else z=read(),Query_1(x,y,z%ha); 99 } 100 }return 0; 101 }
T2:LuoguP4114 Qtree1
单调修改+区间查询，线段树是板子不讲了
树剖部分：因为修改的是加边的时候的第k条边，就用到链式前向星的性质了...自己手推一下应该改哪条边即可
（我的代码线段树打的是区间修改还支持区间加的...主要是模板懒得改了，不影响树剖部分的阅读性）
1 // luogu-judger-enable-o2 2 #include<cstdio> 3 #include<iostream> 4 #include<cstring> 5 #define int long long 6 using namespace std; 7 inline int read(){ 8 int ans=0,f=1;char chr=getchar(); 9 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 10 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 11 return ans*f; 12 }const int M = 100005;char opt[10]; 13 int n,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,fa[M],dep[M],sz[M],b[M],a[M],son[M],idx[M],tp[M],mx[M<<2],lz1[M<<2],lz2[M<<2],rk[M],x,y,z; 14 inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;} 15 void dfs1(int x,int f){ 16 dep[x]=dep[f]+1;sz[x]=1;fa[x]=f; 17 for(int i=head[x];i;i=nxt[i]){ 18 if(ver[i]==f) continue; 19 b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]]; 20 if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i]; 21 } 22 }int t; 23 void dfs2(int x,int topf){ 24 tp[x]=topf;idx[x]=++t;a[t]=b[x]; 25 if(!son[x]) return; 26 dfs2(son[x],topf); 27 for(int i=head[x];i;i=nxt[i]) 28 if(!idx[ver[i]]) dfs2(ver[i],ver[i]); 29 } 30 #define ls (i<<1) 31 #define rs (i<<1|1) 32 #define mid (l+r>>1) 33 inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);} 34 inline void Push_Down(int i){ 35 if(lz1[i]!=-1) 36 mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1; 37 if(!lz2[i]) return; 38 lz2[ls]+=lz2[i],lz2[rs]+=lz2[i]; 39 mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0; 40 } 41 void Build(int i,int l,int r){lz1[i]=-1; 42 if(l==r){mx[i]=a[l];return;} 43 Build(ls,l,mid),Build(rs,mid+1,r); 44 Push_Up(i); 45 } 46 void Update_1(int i,int l,int r,int ql,int qr,int x){ 47 if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;} 48 Push_Down(i); 49 if(ql<=mid) Update_1(ls,l,mid,ql,qr,x); 50 if(qr>mid) Update_1(rs,mid+1,r,ql,qr,x); 51 Push_Up(i); 52 } 53 void Update_2(int i,int l,int r,int ql,int qr,int x){ 54 if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;} 55 Push_Down(i); 56 if(ql<=mid) Update_2(ls,l,mid,ql,qr,x); 57 if(qr>mid) Update_2(rs,mid+1,r,ql,qr,x); 58 Push_Up(i); 59 } 60 int Query(int i,int l,int r,int ql,int qr){ 61 if(ql<=l&&r<=qr) return mx[i]; 62 int ans=0;Push_Down(i); 63 if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr)); 64 if(qr>mid) ans=max(ans,Query(rs,mid+1,r,ql,qr)); 65 return Push_Up(i),ans; 66 } 67 inline void Change(int x,int y){if(dep[ver[2*x-1]]<dep[ver[2*x]]) x=ver[2*x];else x=ver[2*x-1];Update_1(1,1,n,idx[x],idx[x],y);} 68 inline void Max(int x,int y){ 69 int maxn=0,t=0; 70 if(x==y) puts("0"); 71 if(x==y) return; 72 while(tp[x]!=tp[y]){ 73 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 74 t=Query(1,1,n,idx[tp[x]],idx[x]); 75 maxn=max(maxn,t); 76 x=fa[tp[x]]; 77 }if(dep[x]>dep[y]) swap(x,y); 78 t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn); 79 printf("%lld\n",maxn); 80 } 81 signed main(){ 82 n=read(); 83 for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z); 84 dfs1(1,0);dfs2(1,1);Build(1,1,n); 85 while(1){ 86 scanf("%s",opt); 87 if(opt[1]=='O') return 0; 88 if(opt[1]=='H')x=read(),y=read(),Change(x,y); 89 else x=read(),y=read(),Max(x,y); 90 } 91 return 0; 92 }
T3:LuoguP4315 月下“毛景树”
知道为什么上一题要写区间加了吗...因为我是先做这题才做上面那题的!!!
难点是线段树，开两个lazy_tag(lz1,lz2),lz1记录区间覆盖,lz2记录区间加，更新顺序很重要，不过这是线段树部分注意的，这里既然是江树剖，那就不具体讲实现线段树了
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define int long long 5 using namespace std; 6 inline int read(){ 7 int ans=0,f=1;char chr=getchar(); 8 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 9 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 10 return ans*f; 11 }const int M = 100005;char opt[10]; 12 int n,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,fa[M],dep[M],sz[M],b[M],a[M],son[M],idx[M],tp[M],mx[M<<2],lz1[M<<2],lz2[M<<2],rk[M],x,y,z; 13 inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;} 14 void dfs1(int x,int f){ 15 dep[x]=dep[f]+1;sz[x]=1;fa[x]=f; 16 for(int i=head[x];i;i=nxt[i]){ 17 if(ver[i]==f) continue; 18 b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]]; 19 if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i]; 20 } 21 }int t; 22 void dfs2(int x,int topf){ 23 tp[x]=topf;idx[x]=++t;a[t]=b[x]; 24 if(!son[x]) return; 25 dfs2(son[x],topf); 26 for(int i=head[x];i;i=nxt[i]) 27 if(!idx[ver[i]]) dfs2(ver[i],ver[i]); 28 } 29 #define ls (i<<1) 30 #define rs (i<<1|1) 31 #define mid (l+r>>1) 32 inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);} 33 inline void Push_Down(int i){ 34 if(lz1[i]!=-1) 35 mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1; 36 if(!lz2[i]) return; 37 lz2[ls]+=lz2[i],lz2[rs]+=lz2[i]; 38 mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0; 39 } 40 void Build(int i,int l,int r){lz1[i]=-1; 41 if(l==r){mx[i]=a[l];return;} 42 Build(ls,l,mid),Build(rs,mid+1,r); 43 Push_Up(i); 44 } 45 void Update_1(int i,int l,int r,int ql,int qr,int x){ 46 if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;} 47 Push_Down(i); 48 if(ql<=mid) Update_1(ls,l,mid,ql,qr,x); 49 if(qr>mid) Update_1(rs,mid+1,r,ql,qr,x); 50 Push_Up(i); 51 } 52 void Update_2(int i,int l,int r,int ql,int qr,int x){ 53 if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;} 54 Push_Down(i); 55 if(ql<=mid) Update_2(ls,l,mid,ql,qr,x); 56 if(qr>mid) Update_2(rs,mid+1,r,ql,qr,x); 57 Push_Up(i); 58 } 59 int Query(int i,int l,int r,int ql,int qr){ 60 if(ql<=l&&r<=qr) return mx[i]; 61 int ans=0;Push_Down(i); 62 if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr)); 63 if(qr>mid) ans=max(ans,Query(rs,mid+1,r,ql,qr)); 64 return Push_Up(i),ans; 65 } 66 inline void Change(int x,int y){if(dep[ver[2*x-1]]<dep[ver[2*x]]) x=ver[2*x];else x=ver[2*x-1];Update_1(1,1,n,idx[x],idx[x],y);} 67 inline void Cover(int x,int y,int z){ 68 while(tp[x]!=tp[y]){ 69 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 70 Update_1(1,1,n,idx[tp[x]],idx[x],z); 71 x=fa[tp[x]]; 72 }if(dep[x]>dep[y]) swap(x,y); 73 Update_1(1,1,n,idx[x]+1,idx[y],z); 74 } 75 inline void Add(int x,int y,int z){ 76 while(tp[x]!=tp[y]){ 77 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 78 Update_2(1,1,n,idx[tp[x]],idx[x],z); 79 x=fa[tp[x]]; 80 }if(dep[x]>dep[y]) swap(x,y); 81 Update_2(1,1,n,idx[x]+1,idx[y],z); 82 } 83 inline void Max(int x,int y){ 84 int maxn=0,t=0; 85 while(tp[x]!=tp[y]){ 86 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 87 t=Query(1,1,n,idx[tp[x]],idx[x]); 88 maxn=max(maxn,t); 89 x=fa[tp[x]]; 90 }if(dep[x]>dep[y]) swap(x,y); 91 t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn); 92 printf("%lld\n",maxn); 93 } 94 signed main(){ 95 n=read(); 96 for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z); 97 dfs1(1,0);dfs2(1,1);Build(1,1,n); 98 while(1){ 99 scanf("%s",opt); 100 if(opt[1]=='t') return 0; 101 if(opt[1]=='h')x=read(),y=read(),Change(x,y); 102 else if(opt[1]=='o')x=read(),y=read(),z=read(),Cover(x,y,z); 103 else if(opt[1]=='d')x=read(),y=read(),z=read(),Add(x,y,z); 104 else x=read(),y=read(),Max(x,y); 105 } 106 return 0; 107 }
还是板子啊...不讲了...ZJOI也是有简单的时候的啊！
（这是很久很久以前码的...可能码风比较神奇）
1 // luogu-judger-enable-o2 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define int long long 7 #define inf 1000000000 8 using namespace std; 9 inline int read(){ 10 char chr=getchar(); int f=1,ans=0; 11 while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();} 12 while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();} 13 return ans*f; 14 } 15 void write(int x){ 16 if(x<0) putchar('-'),x=-x; 17 if(x>9) write(x/10); 18 putchar(x%10+'0'); 19 } 20 const int M=300005; 21 int n,head[M<<1],nxt[M<<1],ver[M<<1],son[M],ttot,fa[M],dfn[M],top[M],d[M],tot[M],a[M],b[M],cnt,sum[M<<1],t[M<<1]; 22 inline void add(int x,int y){ver[++ttot]=y;nxt[ttot]=head[x];head[x]=ttot;} 23 void dfs1(int x,int ff){ 24 d[x]=d[ff]+1;tot[x]=1;fa[x]=ff; 25 for(int i=head[x];i;i=nxt[i]){ 26 if(ver[i]==ff) continue; 27 dfs1(ver[i],x); 28 tot[x]+=tot[ver[i]]; 29 if(tot[son[x]]<tot[ver[i]]) son[x]=ver[i]; 30 } 31 } 32 void dfs2(int x,int topf){ 33 dfn[x]=++cnt;a[cnt]=b[x];top[x]=topf; 34 if(son[x]) dfs2(son[x],topf); 35 for(int i=head[x];i;i=nxt[i]) 36 if(!dfn[ver[i]]) dfs2(ver[i],ver[i]); 37 } 38 #define ls i<<1 39 #define rs i<<1|1 40 inline void Push_Up(int i){t[i]=max(t[ls],t[rs]);sum[i]=sum[ls]+sum[rs];} 41 void Build(int i,int l,int r){ 42 if(l==r){t[i]=sum[i]=a[l];return;}int mid=l+r>>1; 43 Build(ls,l,mid);Build(rs,mid+1,r); 44 Push_Up(i); 45 } 46 int Query_Max(int i,int l,int r,int ql,int qr){ 47 if(ql<=l&&r<=qr) return t[i]; 48 int maxn=-inf,mid=l+r>>1; 49 if(ql<=mid) maxn=max(Query_Max(ls,l,mid,ql,qr),maxn); 50 if(qr>mid) maxn=max(Query_Max(rs,mid+1,r,ql,qr),maxn); 51 return maxn; 52 } 53 int Query_Sum(int i,int l,int r,int ql,int qr){ 54 if(ql<=l&&r<=qr) return sum[i]; 55 int ans=0,mid=l+r>>1; 56 if(ql<=mid) ans+=Query_Sum(ls,l,mid,ql,qr); 57 if(qr>mid) ans+=Query_Sum(rs,mid+1,r,ql,qr); 58 return ans; 59 } 60 void Updata(int i,int l,int r,int pos,int x){ 61 if(l==r){t[i]=sum[i]=x;return;} 62 int mid=l+r>>1; 63 if(pos<=mid) Updata(ls,l,mid,pos,x); 64 else Updata(rs,mid+1,r,pos,x); 65 Push_Up(i); 66 } 67 inline void Tree_Sum(int x,int y){ 68 int ans=0; 69 while(top[x]!=top[y]){ 70 if(d[top[x]]<d[top[y]]) swap(x,y); 71 ans+=Query_Sum(1,1,n,dfn[top[x]],dfn[x]); 72 x=fa[top[x]]; 73 }if(d[x]>d[y]) swap(x,y); 74 ans+=Query_Sum(1,1,n,dfn[x],dfn[y]); 75 printf("%lld\n",ans); 76 } 77 inline void Tree_Max(int x,int y){ 78 int ans=-inf; 79 while(top[x]!=top[y]){ 80 if(d[top[x]]<d[top[y]]) swap(x,y); 81 ans=max(Query_Max(1,1,n,dfn[top[x]],dfn[x]),ans); 82 x=fa[top[x]]; 83 }if(d[x]>d[y]) swap(x,y); 84 ans=max(Query_Max(1,1,n,dfn[x],dfn[y]),ans); 85 printf("%lld\n",ans); 86 }int x,y,T;char opt[100]; 87 signed main(){ 88 n=read(); 89 for(int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x); 90 for(int i=1;i<=n;i++) b[i]=read(); 91 dfs1(1,0),dfs2(1,1);Build(1,1,n);T=read(); 92 while(T--){ 93 scanf("%s",opt+1);x=read(),y=read(); 94 if(opt[strlen(opt+1)]=='X') Tree_Max(x,y); 95 else if(opt[strlen(opt+1)]=='M') Tree_Sum(x,y); 96 else Updata(1,1,n,dfn[x],y); 97 } 98 return 0; 99 }
T5:P4949 最短距离
基环树上的树剖
把非树边拎出来单独计算即可
非树边可以在dfs1的时候记录下来...
之后这条边就不算进去了，每次询问和更改都单独处理这条边，分类讨论即可
Tip:我的线段树打法因为传参多，常数有点大...但是貌似比一些写树状数组的人还要快好多...
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define int long long 5 using namespace std; 6 inline int read(){ 7 int ans=0,f=1;char chr=getchar(); 8 while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();} 9 while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();} 10 return ans*f; 11 }const int M=500010; 12 int aa[M],bb[M]; 13 int n,m,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot=1,b[M],idx[M],dep[M],son[M],fa[M],sz[M],ext,frm[M<<1],tp[M],mn[M<<2],a[M],x,y,z,opt; 14 inline void add(int x,int y,int z){ver[++tot]=y,nxt[tot]=head[x],val[tot]=z,frm[tot]=x,head[x]=tot;} 15 void dfs1(int x,int f){ 16 dep[x]=dep[f]+1,sz[x]=1; 17 for(int i=head[x];i;i=nxt[i]){ 18 if(f==ver[i]) continue; 19 if(dep[ver[i]]){ext=i;continue;} 20 b[ver[i]]=val[i];fa[ver[i]]=x; 21 dfs1(ver[i],x);sz[x]+=sz[ver[i]]; 22 if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i]; 23 } 24 }int t; 25 void dfs2(int x,int topf){ 26 idx[x]=++t;tp[x]=topf;a[t]=b[x]; 27 if(!son[x]) return; 28 dfs2(son[x],topf); 29 for(int i=head[x];i;i=nxt[i]) 30 if(!idx[ver[i]]&&i!=ext) dfs2(ver[i],ver[i]); 31 } 32 #define ls (i<<1) 33 #define rs (i<<1|1) 34 #define mid (l+r>>1) 35 void Push_Up(int i){mn[i]=mn[ls]+mn[rs];} 36 void Build(int i,int l,int r){ 37 if(l==r){mn[i]=a[l];return;} 38 Build(ls,l,mid),Build(rs,mid+1,r); 39 Push_Up(i); 40 } 41 void Update(int i,int l,int r,int p,int x){ 42 if(l==r){mn[i]=x;return;} 43 if(p<=mid) Update(ls,l,mid,p,x); 44 else Update(rs,mid+1,r,p,x); 45 Push_Up(i); 46 } 47 int Query(int i,int l,int r,int ql,int qr){ 48 if(ql<=l&&r<=qr)return mn[i]; 49 int ans=0; 50 if(ql<=mid) ans+=Query(ls,l,mid,ql,qr); 51 if(qr>mid) ans+=Query(rs,mid+1,r,ql,qr); 52 return ans; 53 } 54 void Change(int x,int z){ 55 int y=bb[x];x=aa[x]; 56 if(x==ver[ext]&&y==frm[ext]||x==ver[ext^1]&&y==frm[ext^1]){val[ext]=val[ext^1]=z;return;} 57 if(dep[x]<dep[y]) x=y; 58 Update(1,1,n,idx[x],z); 59 } 60 int Sum(int x,int y){ 61 int sum=0; 62 while(tp[x]!=tp[y]){ 63 if(dep[tp[x]]<dep[tp[y]]) swap(x,y); 64 sum+=Query(1,1,n,idx[tp[x]],idx[x]); 65 x=fa[tp[x]]; 66 }if(dep[x]>dep[y]) swap(x,y); 67 sum+=Query(1,1,n,idx[x]+1,idx[y]); 68 return sum; 69 } 70 void Q_Min(int x,int y){ 71 int ans=Sum(x,y); 72 int t1=Sum(x,frm[ext])+Sum(ver[ext],y)+val[ext]; 73 int t2=Sum(x,ver[ext])+Sum(frm[ext],y)+val[ext]; 74 ans=min(t1,ans); 75 ans=min(t2,ans); 76 printf("%lld\n",ans); 77 } 78 signed main(){ 79 n=read(),m=read(); 80 for(int i=1;i<=n;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),aa[i]=x,bb[i]=y; 81 dfs1(1,0);dfs2(1,1);Build(1,1,n); 82 while(m--){ 83 opt=read();x=read(),y=read(); 84 if(opt==1) Change(x,y); 85 else Q_Min(x,y); 86 } 87 return 0; 88 }
查看24道真题和解析
