【博客】树链剖分学习笔记
---同步发表于本人博客---
---安利一波浙江省选2019游记---
这里就不写具体实现了...只是为刚看懂什么是树链剖分的同学提供习题
其实树剖部分都差不多的，关键是线段树
可以把这里面5题A了大概就可以熟悉树链剖分了...
（头文件被吃掉了，但不是重点qaq,有不会的可以评论留言，或者加我QQ：1134524176）
T1:LuoguP3384 【模板】树链剖分
都说了是模板，那就是模板咯...
考虑线段树实现 区间加、区间和，又是线段树模板...
树剖跳的时候，因为要更新子树，然后这里更新的话直接idx[x]+sz[x]-1就可以了（因为这些编号是相连的）
取模不要漏！！！
// luogu-judger-enable-o2
#include
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
int ans=0,f=1;char chr=getchar();
while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
return ans*f;
}const int M=300005;
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];
inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs1(int x,int f){
sz[x]=1,fa[x]=f,dep[x]=dep[f]+1;
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==f) continue;
dfs1(ver[i],x);
sz[x]+=sz[ver[i]];
if(sz[ver[i]]>sz[son[x]]) son[x]=ver[i];
}
}int t;
void dfs2(int x,int topf){
tp[x]=topf;idx[x]=++t;a[t]=b[x];rk[t]=x;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
inline void Push_Up(int i){sum[i]=(sum[ls]+sum[rs]+ha)%ha;}
inline void Push_Down(int i,int l,int r){
if(!lz[i]) return;
sum[ls]=(sum[ls]+lz[i]*(mid-l+1)%ha)%ha,sum[rs]=(sum[rs]+lz[i]*(r-mid)%ha)%ha;
lz[ls]=(lz[ls]+lz[i])%ha,lz[rs]=(lz[rs]+lz[i])%ha,lz[i]=0;
}
void Build(int i,int l,int r){
if(l==r){sum[i]=a[l];return;}
Build(ls,l,mid),Build(rs,mid+1,r);
Push_Up(i);
}
void Update(int i,int l,int r,int ql,int qr,int z){
if(ql<=l&&r<=qr){sum[i]=((r-l+1)*z+sum[i])%ha;lz[i]=(lz[i]+z)%ha;return;}
Push_Down(i,l,r);
if(ql<=mid) Update(ls,l,mid,ql,qr,z);
if(qr>mid) Update(rs,mid+1,r,ql,qr,z);
Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[i];
Push_Down(i,l,r);int s=0;
if(ql<=mid) s=(s+Query(ls,l,mid,ql,qr))%ha;
if(qr>mid) s=(s+Query(rs,mid+1,r,ql,qr))%ha;
Push_Up(i);
return s;
}
void Query_1(int x,int y,int val){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
Update(1,1,n,idx[tp[x]],idx[x],val);
x=fa[tp[x]];
}
if(dep[x]>dep[y]) swap(x,y);
Update(1,1,n,idx[x],idx[y],val);
}
void Query_2(int x,int y){
int Ans=0;
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
Ans=(Ans+Query(1,1,n,idx[tp[x]],idx[x]))%ha;
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
Ans=(Ans+Query(1,1,n,idx[x],idx[y]))%ha;
printf("%lld\n",Ans);
}
void Query_3(int x,int y){Update(1,1,n,idx[x],idx[x]+sz[x]-1,y%ha);}
void Query_4(int x){printf("%lld\n",Query(1,1,n,idx[x],idx[x]+sz[x]-1));}
int Q_d(int i,int l,int r,int p){
if(l==r)return sum[i];
Push_Up(i);
if(p<=mid) return Q_d(ls,l,mid,p);
else return Q_d(rs,mid+1,r,p);
}
signed main(){
n=read(),m=read(),root=read(),ha=read();
for(int i=1;i<=n;++i) b[i]=read();
for(int i=1,x,y,z;i<n;++i){x=read(),y=read(),add(x,y),add(y,x);}
dfs1(root,0),dfs2(root,root),Build(1,1,n);
while(m--){int opt=read(),x,y,z;
if(opt==4) x=read(),Query_4(x);
else{x=read(),y=read();
if(opt==3) Query_3(x,y%ha);
else if(opt==2) Query_2(x,y);
else z=read(),Query_1(x,y,z%ha);
}
}return 0;
} T2:LuoguP4114 Qtree1
单调修改+区间查询，线段树是板子不讲了
树剖部分：因为修改的是加边的时候的第k条边，就用到链式前向星的性质了...自己手推一下应该改哪条边即可
（我的代码线段树打的是区间修改还支持区间加的...主要是模板懒得改了，不影响树剖部分的阅读性）
// luogu-judger-enable-o2
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
int ans=0,f=1;char chr=getchar();
while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
return ans*f;
}const int M = 100005;char opt[10];
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;
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
void dfs1(int x,int f){
dep[x]=dep[f]+1;sz[x]=1;fa[x]=f;
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==f) continue;
b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]];
if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
}
}int t;
void dfs2(int x,int topf){
tp[x]=topf;idx[x]=++t;a[t]=b[x];
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);}
inline void Push_Down(int i){
if(lz1[i]!=-1)
mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1;
if(!lz2[i]) return;
lz2[ls]+=lz2[i],lz2[rs]+=lz2[i];
mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0;
}
void Build(int i,int l,int r){lz1[i]=-1;
if(l==r){mx[i]=a[l];return;}
Build(ls,l,mid),Build(rs,mid+1,r);
Push_Up(i);
}
void Update_1(int i,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;}
Push_Down(i);
if(ql<=mid) Update_1(ls,l,mid,ql,qr,x);
if(qr>mid) Update_1(rs,mid+1,r,ql,qr,x);
Push_Up(i);
}
void Update_2(int i,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;}
Push_Down(i);
if(ql<=mid) Update_2(ls,l,mid,ql,qr,x);
if(qr>mid) Update_2(rs,mid+1,r,ql,qr,x);
Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return mx[i];
int ans=0;Push_Down(i);
if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr));
if(qr>mid) ans=max(ans,Query(rs,mid+1,r,ql,qr));
return Push_Up(i),ans;
}
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);}
inline void Max(int x,int y){
int maxn=0,t=0;
if(x==y) puts("0");
if(x==y) return;
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
t=Query(1,1,n,idx[tp[x]],idx[x]);
maxn=max(maxn,t);
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn);
printf("%lld\n",maxn);
}
signed main(){
n=read();
for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
dfs1(1,0);dfs2(1,1);Build(1,1,n);
while(1){
scanf("%s",opt);
if(opt[1]=='O') return 0;
if(opt[1]=='H')x=read(),y=read(),Change(x,y);
else x=read(),y=read(),Max(x,y);
}
return 0;
} T3:LuoguP4315 月下“毛景树”
知道为什么上一题要写区间加了吗...因为我是先做这题才做上面那题的!!!
难点是线段树，开两个lazy_tag(lz1,lz2),lz1记录区间覆盖,lz2记录区间加，更新顺序很重要，不过这是线段树部分注意的，这里既然是江树剖，那就不具体讲实现线段树了
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
int ans=0,f=1;char chr=getchar();
while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
return ans*f;
}const int M = 100005;char opt[10];
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;
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
void dfs1(int x,int f){
dep[x]=dep[f]+1;sz[x]=1;fa[x]=f;
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==f) continue;
b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]];
if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
}
}int t;
void dfs2(int x,int topf){
tp[x]=topf;idx[x]=++t;a[t]=b[x];
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);}
inline void Push_Down(int i){
if(lz1[i]!=-1)
mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1;
if(!lz2[i]) return;
lz2[ls]+=lz2[i],lz2[rs]+=lz2[i];
mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0;
}
void Build(int i,int l,int r){lz1[i]=-1;
if(l==r){mx[i]=a[l];return;}
Build(ls,l,mid),Build(rs,mid+1,r);
Push_Up(i);
}
void Update_1(int i,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;}
Push_Down(i);
if(ql<=mid) Update_1(ls,l,mid,ql,qr,x);
if(qr>mid) Update_1(rs,mid+1,r,ql,qr,x);
Push_Up(i);
}
void Update_2(int i,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;}
Push_Down(i);
if(ql<=mid) Update_2(ls,l,mid,ql,qr,x);
if(qr>mid) Update_2(rs,mid+1,r,ql,qr,x);
Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return mx[i];
int ans=0;Push_Down(i);
if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr));
if(qr>mid) ans=max(ans,Query(rs,mid+1,r,ql,qr));
return Push_Up(i),ans;
}
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);}
inline void Cover(int x,int y,int z){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
Update_1(1,1,n,idx[tp[x]],idx[x],z);
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
Update_1(1,1,n,idx[x]+1,idx[y],z);
}
inline void Add(int x,int y,int z){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
Update_2(1,1,n,idx[tp[x]],idx[x],z);
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
Update_2(1,1,n,idx[x]+1,idx[y],z);
}
inline void Max(int x,int y){
int maxn=0,t=0;
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
t=Query(1,1,n,idx[tp[x]],idx[x]);
maxn=max(maxn,t);
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn);
printf("%lld\n",maxn);
}
signed main(){
n=read();
for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
dfs1(1,0);dfs2(1,1);Build(1,1,n);
while(1){
scanf("%s",opt);
if(opt[1]=='t') return 0;
if(opt[1]=='h')x=read(),y=read(),Change(x,y);
else if(opt[1]=='o')x=read(),y=read(),z=read(),Cover(x,y,z);
else if(opt[1]=='d')x=read(),y=read(),z=read(),Add(x,y,z);
else x=read(),y=read(),Max(x,y);
}
return 0;
} 还是板子啊...不讲了...ZJOI也是有简单的时候的啊！
（这是很久很久以前码的...可能码风比较神奇）
// luogu-judger-enable-o2
#include
#include
#include
#include
#define int long long
#define inf 1000000000
using namespace std;
inline int read(){
char chr=getchar(); int f=1,ans=0;
while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)) {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
return ans*f;
}
void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int M=300005;
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];
inline void add(int x,int y){ver[++ttot]=y;nxt[ttot]=head[x];head[x]=ttot;}
void dfs1(int x,int ff){
d[x]=d[ff]+1;tot[x]=1;fa[x]=ff;
for(int i=head[x];i;i=nxt[i]){
if(ver[i]==ff) continue;
dfs1(ver[i],x);
tot[x]+=tot[ver[i]];
if(tot[son[x]]<tot[ver[i]]) son[x]=ver[i];
}
}
void dfs2(int x,int topf){
dfn[x]=++cnt;a[cnt]=b[x];top[x]=topf;
if(son[x]) dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(!dfn[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls i<<1
#define rs i<<1|1
inline void Push_Up(int i){t[i]=max(t[ls],t[rs]);sum[i]=sum[ls]+sum[rs];}
void Build(int i,int l,int r){
if(l==r){t[i]=sum[i]=a[l];return;}int mid=l+r>>1;
Build(ls,l,mid);Build(rs,mid+1,r);
Push_Up(i);
}
int Query_Max(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return t[i];
int maxn=-inf,mid=l+r>>1;
if(ql<=mid) maxn=max(Query_Max(ls,l,mid,ql,qr),maxn);
if(qr>mid) maxn=max(Query_Max(rs,mid+1,r,ql,qr),maxn);
return maxn;
}
int Query_Sum(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return sum[i];
int ans=0,mid=l+r>>1;
if(ql<=mid) ans+=Query_Sum(ls,l,mid,ql,qr);
if(qr>mid) ans+=Query_Sum(rs,mid+1,r,ql,qr);
return ans;
}
void Updata(int i,int l,int r,int pos,int x){
if(l==r){t[i]=sum[i]=x;return;}
int mid=l+r>>1;
if(pos<=mid) Updata(ls,l,mid,pos,x);
else Updata(rs,mid+1,r,pos,x);
Push_Up(i);
}
inline void Tree_Sum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=Query_Sum(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}if(d[x]>d[y]) swap(x,y);
ans+=Query_Sum(1,1,n,dfn[x],dfn[y]);
printf("%lld\n",ans);
}
inline void Tree_Max(int x,int y){
int ans=-inf;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=max(Query_Max(1,1,n,dfn[top[x]],dfn[x]),ans);
x=fa[top[x]];
}if(d[x]>d[y]) swap(x,y);
ans=max(Query_Max(1,1,n,dfn[x],dfn[y]),ans);
printf("%lld\n",ans);
}int x,y,T;char opt[100];
signed main(){
n=read();
for(int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
for(int i=1;i<=n;i++) b[i]=read();
dfs1(1,0),dfs2(1,1);Build(1,1,n);T=read();
while(T--){
scanf("%s",opt+1);x=read(),y=read();
if(opt[strlen(opt+1)]=='X') Tree_Max(x,y);
else if(opt[strlen(opt+1)]=='M') Tree_Sum(x,y);
else Updata(1,1,n,dfn[x],y);
}
return 0;
} T5:P4949 最短距离
基环树上的树剖
把非树边拎出来单独计算即可
非树边可以在dfs1的时候记录下来...
之后这条边就不算进去了，每次询问和更改都单独处理这条边，分类讨论即可
Tip:我的线段树打法因为传参多，常数有点大...但是貌似比一些写树状数组的人还要快好多...
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
int ans=0,f=1;char chr=getchar();
while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
return ans*f;
}const int M=500010;
int aa[M],bb[M];
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;
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;}
void dfs1(int x,int f){
dep[x]=dep[f]+1,sz[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(f==ver[i]) continue;
if(dep[ver[i]]){ext=i;continue;}
b[ver[i]]=val[i];fa[ver[i]]=x;
dfs1(ver[i],x);sz[x]+=sz[ver[i]];
if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
}
}int t;
void dfs2(int x,int topf){
idx[x]=++t;tp[x]=topf;a[t]=b[x];
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=head[x];i;i=nxt[i])
if(!idx[ver[i]]&&i!=ext) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
void Push_Up(int i){mn[i]=mn[ls]+mn[rs];}
void Build(int i,int l,int r){
if(l==r){mn[i]=a[l];return;}
Build(ls,l,mid),Build(rs,mid+1,r);
Push_Up(i);
}
void Update(int i,int l,int r,int p,int x){
if(l==r){mn[i]=x;return;}
if(p<=mid) Update(ls,l,mid,p,x);
else Update(rs,mid+1,r,p,x);
Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return mn[i];
int ans=0;
if(ql<=mid) ans+=Query(ls,l,mid,ql,qr);
if(qr>mid) ans+=Query(rs,mid+1,r,ql,qr);
return ans;
}
void Change(int x,int z){
int y=bb[x];x=aa[x];
if(x==ver[ext]&&y==frm[ext]||x==ver[ext^1]&&y==frm[ext^1]){val[ext]=val[ext^1]=z;return;}
if(dep[x]<dep[y]) x=y;
Update(1,1,n,idx[x],z);
}
int Sum(int x,int y){
int sum=0;
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
sum+=Query(1,1,n,idx[tp[x]],idx[x]);
x=fa[tp[x]];
}if(dep[x]>dep[y]) swap(x,y);
sum+=Query(1,1,n,idx[x]+1,idx[y]);
return sum;
}
void Q_Min(int x,int y){
int ans=Sum(x,y);
int t1=Sum(x,frm[ext])+Sum(ver[ext],y)+val[ext];
int t2=Sum(x,ver[ext])+Sum(frm[ext],y)+val[ext];
ans=min(t1,ans);
ans=min(t2,ans);
printf("%lld\n",ans);
}
signed main(){
n=read(),m=read();
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;
dfs1(1,0);dfs2(1,1);Build(1,1,n);
while(m--){
opt=read();x=read(),y=read();
if(opt==1) Change(x,y);
else Q_Min(x,y);
}
return 0;
}
阿里巴巴公司氛围 330人发布
投递兆芯等公司10个岗位 >