终于学到了树剖!!!
前置知识:LCA,树形DP,DFS,邻接表,线段树。
树链剖分
线段树的特点:区间修改,区间查询,线性;
树上差分特点:单点修改,树形区间查询;
现在,如果我们想进行树形区间修改和查询,是否存在一种算法能够做到呢?
搜狗百科对于树剖的定义:树链剖分,计算机术语,指一种对树进行划分的算法,它先通过轻重边剖分将树分为多条链,保证每个点属于且只属于一条链,然后再通过数据结构(树状数组、SBT、SPLAY、线段树等)来维护每一条链。
轻重树链剖分(启发式剖分)
首先明确一些概念:
重儿子:父亲节点的所有儿子中已那个儿子为根的子树节点数目最多(size最大)的节点;
轻儿子:对于每一个非叶子结点,它的儿子中的非重儿子节点
叶子结点既没有重儿子也没有轻儿子
重边:父亲节点和重儿子所连的边
轻边:剩下的边即为轻边
重链:相邻重边连起来的 连接一条重儿子的链叫重链
对于叶子节点,若其为轻儿子,则有一条以自己为起点的长度为1的链
每一条重链以轻儿子为起点
dfs1()
这个dfs要处理几件事情:
标记每个点的深度dep[N]
标记每个点的父亲fa[N]
标记每个非叶子结点的子树大小siz[N]
标记每个非叶子结点的重儿子编号son[N]
void dfs1(int u,int Fa){ dep[u]=dep[Fa]+1; fa[u]=Fa; siz[u]=1; int maxson=-1; for(int i=h[u];i;i=e[i].nxt){ int v=e[i].to; if(v==Fa) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxson) son[u]=v,maxson=siz[v]; } }
dfs2()
这个dfs2也要处理几件事情
标记每个点的新编号id[N]
赋值每个点的初始值到新编号上wt[N]
处理每个点所在链的顶端
处理每条链
顺序:先处理重儿子在处理轻儿子
void dfs2(int u,int topf){ id[u]=++cnt; wt[cnt]=w[u]; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } }
由于处理顺序是先处理重儿子再处理轻儿子,所以
每一条重链的新编号是连续的
因为是dfs,所以每一个子树的新编号也是连续的
现在回顾一下我们要处理的问题
处理任意两点间的路径和
处理一点及其子树的点权和
修改任意两点间路径上的点权
修改一点及其子树的点权
1、当我们处理任意两点间路径时:
对于点 u,v,u所在链的顶点深度 ≤ v所在链的顶点深度
ans+=u到u所在链顶端 这一段区间的点权和
把u调到u所在链顶端的点的父亲节点
重复执行以上步骤,直到两个点位于同一条链,此时再加上这两点间的区间和即可
int qRange(int u,int v){ int ans=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); res=0; query(1,id[top[u]],id[u]); ans+=res; u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); res=0; query(1,id[u],id[v]); ans+=res; return ans%mod; }
2、处理一点及其子树的点权和:
每个非叶子结点,子树的编号都是连续的,线段树区间查询即可
int qSon(int u){ res=0; query(1,id[u],id[u]+siz[u]-1); return res%mod; }
当然,区间修改也一样
void updRange(int u,int v,int k){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); update(1,id[top[u]],id[u],k); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); update(1,id[u],id[v],k); } void updSon(int u,int k){ update(1,id[u],id[u]+siz[u]-1,k); }
建树
这里我们采用线段树维护链,按照题意建树即可。
代码
#include<bits/stdc++.h> #define int long long #define ls(r) r<<1 #define rs(r) r<<1|1 using namespace std; const int N=1e6+10; int n,q,tot,cnt,root,res,mod; int h[N],w[N],wt[N]; int son[N],id[N],fa[N],dep[N],siz[N],top[N]; struct node{ int to,nxt,w; }e[N<<1]; struct tree{ int l,r,ans,tag; }t[N<<2]; void add(int u,int v){ e[++tot].to=v; e[tot].nxt=h[u]; h[u]=tot; } void f(int p,int l,int r,int k){ t[p].tag+=k; t[p].ans+=(r-l+1)*k; t[p].ans%=mod; } void push_down(int p){ int mid=t[p].l+t[p].r>>1; f(ls(p),t[p].l,mid,t[p].tag); f(rs(p),mid+1,t[p].r,t[p].tag); t[p].tag=0; } void push_up(int p){ t[p].ans=t[ls(p)].ans+t[rs(p)].ans; } void build(int l,int r,int p){ t[p].l=l,t[p].r=r; if(l==r){ t[p].ans=wt[l];return; } int mid=l+r>>1; build(l,mid,ls(p)); build(mid+1,r,rs(p)); push_up(p); } void query(int p,int l,int r){ if(l<=t[p].l&&t[p].r<=r){ res+=t[p].ans;return; } if(t[p].tag) push_down(p); int mid=t[p].l+t[p].r>>1; if(l<=mid) query(ls(p),l,r); if(r>mid) query(rs(p),l,r); } void update(int p,int l,int r,int k){ if(l<=t[p].l&&t[p].r<=r){ t[p].tag+=k;t[p].ans+=k*(t[p].r-t[p].l+1);return ; } push_down(p); int mid=t[p].l+t[p].r>>1; if(l<=mid) update(ls(p),l,r,k); if(r>mid) update(rs(p),l,r,k); push_up(p); } int qRange(int u,int v){ int ans=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); res=0; query(1,id[top[u]],id[u]); ans+=res; u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); res=0; query(1,id[u],id[v]); ans+=res; return ans%mod; } void updRange(int u,int v,int k){ while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); update(1,id[top[u]],id[u],k); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); update(1,id[u],id[v],k); } int qSon(int u){ res=0; query(1,id[u],id[u]+siz[u]-1); return res%mod; } void updSon(int u,int k){ update(1,id[u],id[u]+siz[u]-1,k); } void dfs1(int u,int Fa){ dep[u]=dep[Fa]+1; fa[u]=Fa; siz[u]=1; int maxson=-1; for(int i=h[u];i;i=e[i].nxt){ int v=e[i].to; if(v==Fa) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxson) son[u]=v,maxson=siz[v]; } } void dfs2(int u,int topf){ id[u]=++cnt; wt[cnt]=w[u]; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=h[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } signed main(){ cin>>n>>q>>root>>mod; for(int i=1;i<=n;++i) cin>>w[i]; for(int i=1,u,v;i<n;++i){ cin>>u>>v;add(u,v),add(v,u); } dfs1(root,0); dfs2(root,root); build(1,n,1); while(q--){ int k,u,v,x; cin>>k; if(k==1){ cin>>u>>v>>x; updRange(u,v,x); } else if(k==2){ cin>>u>>v; cout<<qRange(u,v)%mod<<endl; } else if(k==3){ cin>>u>>v; updSon(u,v); } else{ cin>>u; cout<<qSon(u)%mod<<endl; } } return 0; }
标签:剖分,int,siz,top,树链,dep,void,id From: https://www.cnblogs.com/buleeyes/p/17171305.html