树链剖分

首先看下dfs序

dfs序解决的子树的问题

树链剖分解决的是链的问题

这个dfs序把这个树的节点都标上号，类似于先序遍历可以看出红色里的子树序号都是连在一起的，这样就可以用dfs序求子树。

这个子树的序号是连续的那么比如红色里的是2-4那么就可以每个节点+v 求和 求最大值(可以用线段树维护)等等。。

int time = 0; inline void dfs(int x, int fa) { in[x] = ++time; //进入的时间戳 num[time] = x; //生成新的线性结构 for(int i = 0; i < G[x].size(); i++) { int cnt = G[x][i]; if(cnt == fa) continue; dfs(cnt, x); } out[x] = time; //出去的时间戳 }

 

这样树链剖分其实就是用到了dfs序的思想  只不过复杂一些了，它是首先搞重链当dfs序，然后在是轻链。

 

 

首先明确概念：

重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；

轻儿子：父亲节点中除了重儿子以外的儿子；

重边：父亲结点和重儿子连成的边；

轻边：父亲节点和轻儿子连成的边；

重链：由多条重边连接而成的路径；

轻链：由多条轻边连接而成的路径；

比如上面这幅图中，用黑线连接的结点都是重结点，其余均是轻结点，

2-11就是重链，2-5就是轻链，用红点标记的就是该结点所在重链的起点，也就是下文提到的top结点，

还有每条边的值其实是进行dfs时的执行序号。

我们要做的就是（树链剖分的实现）：

1，对于一个点我们首先求出它所在的子树大小,找到它的重儿子（即处理出size,sonsize,son数组），

解释:比如说点1，它有三个儿子2，3，4

2所在子树的大小是5

3所在子树的大小是2

4所在子树的大小是6

那么1的重儿子是4

ps:如果一个点的多个儿子所在子树大小相等且最大

那随便找一个当做它的重儿子就好了

叶节点没有重儿子，非叶节点有且只有一个重儿子

 

2，在dfs1过程中顺便记录其父亲以及深度（即处理出fa,dep数组），

void dfs1(int u,int fa,int depth) //当前节点、父节点、层次深度 { f[u]=fa; d[u]=depth; size[u]=1; //这个点本身size=1 for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue; dfs1(v,u,depth+1); //层次深度+1 size[u]+=size[v]; //子节点的size已被处理，用它来更新父节点的size if(size[v]>size[son[u]]) son[u]=v; //选取size最大的作为重儿子 } } //进入 dfs1(root,0,1);

 

3，第二遍dfs，然后连接重链，同时标记每一个节点的dfs序，并且为了用数据结构来维护重链，我们在dfs时保证一条重链上各个节点dfs序连续（即处理出数组top,id,rktop,id,rk）

void dfs2(int u,int t) //当前节点、重链顶端 { top[u]=t; id[u]=++cnt; //标记dfs序 rk[cnt]=u; //序号cnt对应节点u if(!son[u]) return; dfs2(son[u],t); /*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/ for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(v!=son[u]&&v!=f[u]) dfs2(v,v); //一个点位于轻链底端，那么它的top必然是它本身 } }

 

4，两遍dfs就是树链剖分的主要处理，通过dfs我们已经保证一条重链上各个节点dfs序连续，那么可以想到，我们可以通过数据结构（以线段树为例）来维护一条重链的信息

回顾上文的那个题目，修改和查询操作原理是类似的，以查询操作为例，其实就是个LCA，不过这里使用了top来进行加速，因为top可以直接跳转到该重链的起始结点，轻链没有起始结点之说，他们的top就是自己。需要注意的是，每次循环只能跳一次，并且让结点深的那个来跳到top的位置，避免两个一起跳从而插肩而过。

在树上修改 查询可以看具体代码解释

如下

/* 树链剖分 落谷： p3384 题意： 操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z 操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和 操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z 操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和 */ #include<bits/stdc++.h> using namespace std; const int maxn=200000+10; int n,m,r,mod; int w[maxn],wt[maxn]; //链式前向星数组，w[]、wt[]初始点权数组 int a[maxn<<2],laz[maxn<<2]; //线段树数组、lazy操作 int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; //son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小, //top[]当前链顶端节点 struct node { int to,next; }edge[maxn<<2]; int head[maxn<<2]; int cc=0; void addedge(int x,int y){//链式前向星加边 edge[cc].to=y; edge[cc].next=head[x]; head[x]=cc++; } //-------------------------------------- 以下为线段树 inline void push_down(int rt,int lenn){ if(laz[rt]){ laz[rt<<1]+=laz[rt]; laz[rt<<1|1]+=laz[rt]; a[rt<<1]+=laz[rt]*(lenn-(lenn>>1)); a[rt<<1|1]+=laz[rt]*(lenn>>1); a[rt<<1]%=mod; a[rt<<1|1]%=mod; laz[rt]=0; } } inline void build(int l,int r,int rt){ if(l==r){ a[rt]=wt[l]; if(a[rt]>mod)a[rt]%=mod; return; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); a[rt]=(a[rt<<1]+a[rt<<1|1])%mod; } inline void update(int L,int R,int k,int l,int r,int rt){ if(L<=l&&r<=R){ laz[rt]+=k; a[rt]+=k*(r-l+1); return; } push_down(rt,r-l+1); int mid=(l+r)>>1; if(L<=mid)update(L,R,k,l,mid,rt<<1); if(R>mid)update(L,R,k,mid+1,r,rt<<1|1); a[rt]=(a[rt<<1]+a[rt<<1|1])%mod; } int query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R){ return a[rt]%mod; } push_down(rt,r-l+1); int sum=0; int mid=(l+r)>>1; if(L<=mid) sum+=query(L,R,l,mid,rt<<1); if(R>mid) sum+=query(L,R,mid+1,r,rt<<1|1); return sum; } //---------------------------------以上为线段树 inline int qRange(int x,int y){ int ans=0; while(top[x]!=top[y]){//当两个点不在同一条链上 if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点 ans+=query(id[top[x]],id[x],1,n,1);//ans加上x点到x所在链顶端 这一段区间的点权和 ans%=mod;//按题意取模 x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点 } //直到两个点处于一条链上 if(dep[x]>dep[y])swap(x,y);//把x点深度更深的那个点 ans+=query(id[x],id[y],1,n,1);//这时再加上此时两个点的区间和即可 return ans%mod; } inline void updRange(int x,int y,int k){//同上 k%=mod; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); update(id[top[x]],id[x],k,1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(id[x],id[y],k,1,n,1); } inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度 dep[x]=deep;//标记每个点的深度 fa[x]=f;//标记每个点的父亲 siz[x]=1;//标记每个非叶子节点的子树大小 for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(y==f)continue;//若为父亲则continue dfs1(y,x,deep+1);//dfs其儿子 siz[x]+=siz[y];//把它的儿子数加到它身上 if(siz[y]>siz[son[x]]) son[x]=y; } } inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点 id[x]=++cnt;//标记每个点的新编号 wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 top[x]=topf;//这个点所在链的顶端 if(!son[x])return;//如果没有儿子则返回 dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理 for(int i=head[x];i!=-1;i=edge[i].next){ int y=edge[i].to; if(y!=fa[x]&&y!=son[x]) dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 } } int main() { scanf("%d %d %d %d",&n,&m,&r,&mod); memset(head,-1,sizeof(head)); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<n;i++){ int a,b; scanf("%d %d",&a,&b); addedge(a,b);addedge(b,a); } dfs1(r,0,1); dfs2(r,r); build(1,n,1); while(m--){ int k,x,y,z; scanf("%d",&k); if(k==1){ scanf("%d %d %d",&x,&y,&z); updRange(x,y,z); } else if(k==2){ scanf("%d %d",&x,&y); printf("%d\n",qRange(x,y)); } else if(k==3){ scanf("%d %d",&x,&y); update(id[x],id[x]+siz[x]-1,y,1,n,1); } else{ scanf("%d",&x); printf("%d\n",query(id[x],id[x]+siz[x]-1,1,n,1)%mod); } } }