树链剖分
树链剖分是一种对树的分治, 可以把树上的任意一条链分解为 (O(log n)) 条在dfs序上相邻的子链, 便于数据结构(如线段树)来维护.
另外, 子树在dfs序上也是一个连续的区间, 同样可以利用数据结构维护.
重链剖分保证了一些性质:
- 每个点到根的重链条数为 (O(log n)).
Code
//sgt:
// chg(v,l,r,rt,rl,rr) 区间修改
// que(l,r,rt,rl,rr) 区间查询
//树剖
int sz[nsz],fa[nsz],son[nsz],dep[nsz];//got through dfs1
int dfn[nsz],pd=0,idfn[nsz],top[nsz];//got through dfs2
void dfs1(int p){
sz[p]=1;
forg(p,i,v){
if(v==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1;
dfs1(v);
sz[p]+=sz[v];
if(son[p]==0||sz[v]>sz[son[p]])son[p]=v;
}
}
void dfs2(int p){
dfn[++pd]=p,idfn[p]=pd;
top[p]=(p==son[fa[p]]?top[fa[p]]:p);
if(son[p])dfs2(son[p]);
forg(p,i,v){
if(v==fa[p]||v==son[p])continue;
dfs2(v);
}
}
//query template
void treec(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
//do something
chg(v,idfn[top[x]],idfn[x],1,1,n);
//end
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
//also do sth
chg(v,idfn[y],idfn[x],1,1,n);
//end
}
例题: luogu3384-【模板】树链剖分
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;
//---------------------------------------
const int nsz=1e5+50;
int n,m,r,nmod,line[nsz];
//g
struct te{int t,pr;}edge[nsz*2];
int hd[nsz],pe=1;
void adde(int f,int t){edge[++pe]=(te){t,hd[f]};hd[f]=pe;}
void adddb(int f,int t){adde(f,t);adde(t,f);}
#define forg(p,i,v) for(int i=hd[p],v=edge[i].t;i;i=edge[i].pr,v=edge[i].t)
//sgt
void addv(int &a,int b){a=(a+b)%nmod;}
struct tnd{int sum,tag;}tree[nsz*4];
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
void addp(int p,int v,int l){addv(tree[p].sum,(ll)v*l%nmod);addv(tree[p].tag,v);}
void pushd(int p,int l1,int l2){
int tmp=tree[p].tag;
addp(ls(p),tmp,l1);
addp(rs(p),tmp,l2);
tree[p].tag=0;
}
void chg(int v,int l,int r,int rt,int rl,int rr){
if(l<=rl&&rr<=r){addp(rt,v,rr-rl+1);return;}
int mid=(rl+rr)>>1;
if(l<=mid)chg(v,l,r,ls(rt),rl,mid);
if(r>mid)chg(v,l,r,rs(rt),mid+1,rr);
addv(tree[rt].sum,(ll)v*(min(r,rr)-max(l,rl)+1)%nmod);
}
int que(int l,int r,int rt,int rl,int rr){
if(l<=rl&&rr<=r){return tree[rt].sum;}
int mid=(rl+rr)>>1,res=0;
if(tree[rt].tag)pushd(rt,mid-rl+1,rr-mid);
if(l<=mid)res=que(l,r,ls(rt),rl,mid);
if(r>mid)addv(res,que(l,r,rs(rt),mid+1,rr));
return res;
}
void pr(int rt,int rl,int rr){
printf("rt=%d rl=%d rr=%d sum=%d tag=%d
",rt,rl,rr,tree[rt].sum,tree[rt].tag);
if(rl==rr)return;
int mid=(rl+rr)>>1;
pushd(rt,mid-rl+1,rr-mid);
pr(ls(rt),rl,mid);
pr(rs(rt),mid+1,rr);
}
//树剖
int sz[nsz],fa[nsz],son[nsz],dep[nsz];//got through dfs1
int dfn[nsz],pd=0,idfn[nsz],top[nsz];//got through dfs2
void dfs1(int p){
sz[p]=1;
forg(p,i,v){
if(v==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1;
dfs1(v);
sz[p]+=sz[v];
if(son[p]==0||sz[v]>sz[son[p]])son[p]=v;
}
}
void dfs2(int p){
dfn[++pd]=p,idfn[p]=pd;
top[p]=(p==son[fa[p]]?top[fa[p]]:p);
if(son[p])dfs2(son[p]);
forg(p,i,v){
if(v==fa[p]||v==son[p])continue;
dfs2(v);
}
}
int treeq(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
addv(res,que(idfn[top[x]],idfn[x],1,1,n));
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
addv(res,que(idfn[y],idfn[x],1,1,n));
return res;
}
void treec(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
chg(v,idfn[top[x]],idfn[x],1,1,n);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
chg(v,idfn[y],idfn[x],1,1,n);
}
void init(){
dfs1(r),dfs2(r);
rep(i,1,n)chg(line[i],idfn[i],idfn[i],1,1,n);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>r>>nmod;
rep(i,1,n)cin>>line[i];
int a,b,c,d;
rep(i,1,n-1)cin>>a>>b,adddb(a,b);
init();
// pr(1,1,n);
rep(i,1,m){
cin>>a>>b;
switch(a){
case 1:
cin>>c>>d;
treec(b,c,d%nmod);
break;
case 2:
cin>>c;
cout<<treeq(b,c)<<'
';
break;
case 3:
cin>>c;
chg(c%nmod,idfn[b],idfn[b]+sz[b]-1,1,1,n);
break;
case 4:
cout<<que(idfn[b],idfn[b]+sz[b]-1,1,1,n)<<'
';
break;
}
// printf("oper %d
",i);
// pr(1,1,n);
}
return 0;
}
换根
换根对于链显然没有影响.
对于子树, 判断 ( ext {lca}(rt,u)) 和 (u) 的关系. 发现换根后的子树为原子树/原子树的补集. 讨论之后同子树查询.