图论学习笔记 - 树链剖分

定义

树链剖分就是对一棵树分成几条链，把树形变为线性，减少处理难度。

变为线性后，经常跟线段树的知识相连，所以代码量相对比较大

基本概念

树剖可以维护的操作

将树从x到y结点最短路径上所有节点的值都加上z

求树从x到y结点最短路径上所以节点的值之和

将以x为根节点的子树内所有节点值都加上z

求以x为根节点的子树内所有节点值之和

 树剖中的关键词

重儿子：对于每一个非叶子节点，它的儿子中以 那个儿子为根的子树节点数最大的儿子 为该节点的重儿子(也就是选子孙兴旺的)

轻儿子：对于每一个非叶子节点，它的儿子中 非重儿子 的剩下所有儿子均即为轻儿子

注意：叶子节点没有儿子所以不存在重或轻儿子

重边：一个父亲节点连接他的重儿子节点的边称为重边

轻边：同理剩下的即为轻边

重链：相邻重边连起来的 连接一条重儿子 的链叫重链

在这里注意：

对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
 
每一条重链以轻儿子为起点

处理

dfs_1(int x,int f)

我们需要在这次dfs中处理出来以下的几个数据：

标记每个点的深度dep[]
标记每个点的父亲fa[]
标记每个非叶子节点的子树大小(含它自己)
标记每个非叶子节点的重儿子编号son[]

 代码示例：

void dfs_1(int x,int f){ //x为当前节点,f为父节点
	dep[x]=dep[f]+1; //dep代表深度,x的深度自然为它父节点+1
	fa[x]=f; //fa存储的是x的父节点
	siz[x]=1; //siz代表的是x的子树大小,初始化为1,也就是子树只有本身(即为叶子节点)
	int maxson=-1; //后续比较,需要记录最大的子树作为儿子
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f) continue;
		dfs_1(y,x);
		siz[x]+=siz[y]; //更新当前节点x的子树个数
		if(siz[y]>maxson){
			son[x]=y; //记录当前节点x的重儿子是谁
			maxson=siz[y]; //更新每个非叶子节点的重儿子大小
		}
	}
}

dfs_2(int x,int topf)

这次的dfs需要借用上一次的dfs处理出来的数据

标记每个点的新编号
赋值每个点的初始值到新编号上
处理每个点所在链的顶端
处理每条链

 代码示例：

void dfs_2(int x,int topf){ //x是当前节点,topf是x所在重链的最祖先节点
	dfn[x]=++cnt; //dfn是dfs序，也可以理解为重新给节点编号
	at[cnt]=a[x]; //按时间顺序存储值
	top[x]=topf; //记录每个节点x的最祖先节点为topf
	if(!son[x]) return; //如果是叶子节点直接返回就可以
	dfs_2(son[x],topf); //先查找重儿子节点
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]||y==son[x]) continue; //如果y是x的父节点或者重儿子节点直接跳过就行
		dfs_2(y,y);
	}
}

相信大家现在心里有一个问题：为什么要先处理重儿子呢？

其实是根据我们对这棵树的规定，因为我们先遍历重儿子，所以每一条重链上的新编号都是连续的，这样当我们进行两点之间的查询或修改的操作时，就能变成区间修改或区间查询的操作。而对于轻儿子们来说，也是被包含在一个连续区间内的，这样就可以将对某一节点所有子树的查询或修改变成区间修改或区间查询了。

这里给张图，帮助大家理解

现在我们开始维护操作

1. 修改（查询）任意两点间路径

假如我们要求 x，y 两点间路径。设所在链顶端的深度更深的那个点为 x 点(否则可以swap一下)，如果 x，y 在同一条链上，我们可以直接求和，否则我们一直进行以下操作

ans加上x点到x所在链顶端 这一段区间的点权和
 
把x跳到x所在链顶端的那个点的上面一个点

 如果我们直接暴力求解的话，时间复杂度一般是无法接受的

这时就需要用到我们刚才提到的 dfs_2 了

经过两次 dfs 我们已经将一个树形结构的图变成了一个个线性的区间了(每个区间都是一条重链)，所以当我们需要对任意两点路径修改的时候，其实就是对区间进行操作，为了代码的执行效率，我们一般用线段树进行操作。

代码示例：

if(op==1){
	cin>>x>>y>>z;
	z%=p;
	while(top[x]!=top[y]){ //当两个点不在同一条重链上时
		if(dep[top[x]]swap(x,y); //把 x 变成所在链顶端深度更深的点
		change(1,dfn[top[x]],dfn[x],z); //修改 x 到 x 所在链顶端所有的节点
		x=fa[top[x]]; //将 x 变成所在链顶端的父节点,即到另一条重链上
	}
    //当跳出循环后，证明此时 x,y 在同一条重链上
	if(dep[x]>dep[y]) swap(x,y); //注意区间左右的顺序
	change(1,dfn[x],dfn[y],z);
}

查询同理：

if(op==2){
	int tot=0; //用来统计答案
	cin>>x>>y;
	while(top[x]!=top[y]){
		if(dep[top[x]]swap(x,y);
		ans=0;
		find(1,dfn[top[x]],dfn[x]);
		tot+=ans;
		tot%=p;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans=0; //ans 是线段树区间查询时需要用到的变量,每次查询都需要更新为 0
	find(1,dfn[x],dfn[y]);
	tot+=ans;
	cout<
}

2. 修改（查询）以 x 为根节点的子树内所有节点值

还是用最开始的两次 dfs 来进行操作

遍历 dfn 的时候虽然先去重儿子，但是并不影响之后的遍历顺序，也就是说，无论是否先遍历重儿子并不会影响最终以 x 为根节点的子树的所有节点为一段连续的区间。仔细想想，以 x 为根节点的子树的所有节点所表示的区间其实就是 (dfn[x],dfn[x]+siz[x]-1)

代码示例：

if(op==3){ //区间修改
	cin>>x>>z;
	change(1,dfn[x],dfn[x]+siz[x]-1,z);
}
if(op==4){ //区间查询
	ans=0;
	cin>>x;
	find(1,dfn[x],dfn[x]+siz[x]-1);
	cout<
}

最后再把线段树糊上去就可以了

题目链接 - P3384【模板】轻重链剖分/树链剖分

#include
#include
#include
#include
#include
using namespace std;
 
#define int long long
 
const int maxn=2010000;
int n,m,r,p;
int ans;
int tot;
int cnt;
int a[maxn];
int at[maxn];
int head[maxn];
int dfn[maxn];
int lst[maxn];
int dep[maxn];
int fa[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
 
struct edge{
	int to;
	int from;
	int nxt;
}e[2*maxn];
 
struct Tree{
	int l;
	int r;
	int val;
	int lazy;
}tree[4*maxn];
 
void add(int x,int y){
	tot++;
	e[tot].to=y;
	e[tot].from=x;
	e[tot].nxt=head[x];
	head[x]=tot;
}
 
void dfs_1(int x,int f){
	dep[x]=dep[f]+1;
	fa[x]=f;
	siz[x]=1;
	int maxson=-1;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==f) continue;
		dfs_1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>maxson){
			son[x]=y;
			maxson=siz[y];
		}
	}
}
 
void dfs_2(int x,int topf){
	dfn[x]=++cnt;
	at[cnt]=a[x];
	top[x]=topf;
	if(!son[x]) return;
	dfs_2(son[x],topf);
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==fa[x]||y==son[x]) continue;
		dfs_2(y,y);
	}
}
 
void push_up(int rt){
	tree[rt].val=(tree[rt<<1].val%p+tree[rt<<1|1].val%p)%p;
}
 
void build(int rt,int l,int r){
	tree[rt].l=l,tree[rt].r=r;
	if(l==r){
		tree[rt].val=at[l];
		if(tree[rt].val>p) tree[rt].val%=p;
		return;
	}
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}
 
void push_down(int rt){
	tree[rt<<1].lazy+=tree[rt].lazy;
	tree[rt<<1|1].lazy+=tree[rt].lazy;
	tree[rt<<1].val+=(tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].lazy;
	tree[rt<<1|1].val+=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*tree[rt].lazy;
	tree[rt].lazy=0;
}
 
void change(int rt,int a,int b,int c){
	if(tree[rt].l>=a&&tree[rt].r<=b){
		tree[rt].lazy+=c;
		tree[rt].val+=(tree[rt].r-tree[rt].l+1)*c;
		return;
	}
	if(tree[rt].lazy) push_down(rt);
	int mid=tree[rt].l+tree[rt].r>>1;
	if(a<=mid) change(rt<<1,a,b,c);
	if(b>mid) change(rt<<1|1,a,b,c);
	push_up(rt);
}
 
void find(int rt,int a,int b){
	if(tree[rt].l>=a&&tree[rt].r<=b){
		ans=(ans%p+tree[rt].val%p)%p;
		return;
	}
	if(tree[rt].lazy) push_down(rt);
	int mid=tree[rt].l+tree[rt].r>>1;
	if(a<=mid) find(rt<<1,a,b);
	if(b>mid) find(rt<<1|1,a,b);
	return;
}
 
signed main(){
	cin>>n>>m>>r>>p;
	for(int i=1;i<=n;i++) cin>>a[i];
	int x,y;
	for(int i=1;i
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	int op,z;
	dfs_1(r,0);
	dfs_2(r,r);
	build(1,1,n);
	while(m--){
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			z%=p;
			while(top[x]!=top[y]){
				if(dep[top[x]]swap(x,y);
				change(1,dfn[top[x]],dfn[x],z);
				x=fa[top[x]];
			}
			if(dep[x]>dep[y]) swap(x,y);
			change(1,dfn[x],dfn[y],z);
		}
		if(op==2){
			int tot=0;
			cin>>x>>y;
			while(top[x]!=top[y]){
				if(dep[top[x]]swap(x,y);
				ans=0;
				find(1,dfn[top[x]],dfn[x]);
				tot+=ans;
				tot%=p;
				x=fa[top[x]];
			}
			if(dep[x]>dep[y]) swap(x,y);
			ans=0;
			find(1,dfn[x],dfn[y]);
			tot+=ans;
			cout<
		}
		if(op==3){
			cin>>x>>z;
			change(1,dfn[x],dfn[x]+siz[x]-1,z);
		}
		if(op==4){
			ans=0;
			cin>>x;
			find(1,dfn[x],dfn[x]+siz[x]-1);
			cout<
		}
	}
	// system("pause");
	return 0;
}