• 树链剖分，是一种让你代码瞬间增加1kb，轻轻松松飙到两百行的，极其优(bào)美(lì)的毒瘤算法。  

目录

一.概念

二.操作

三.实例

---

一.概念

• 指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。

简单来说，就是：把一棵树拆成若干个不相交的链，然后用一些数据结构去维护这些链。

而我们需要解决的是，如何将树拆分成链状↓↓↓

常见的路径剖分的方法是轻重边剖分，即把树中的边分为轻重两部分；

一些需知概念：

• 重结点：子树结点数目最多的结点；
• 轻节点：父亲节点中除了重结点以外的结点；
• 重边：父亲结点和重结点连成的边；
• 轻边：父亲节点和轻节点连成的边；
• 重链：由多条重边连接而成的路径；
• 轻链：由多条轻边连接而成的路径；

给张图，大概就长介个样子：

用黑线连接的结点都是重结点，其余均是轻结点；

加粗的都是重链，其他就是轻链；

用红点标记的就是该结点所在链的起点，也就是我们提到的top结点；

用数组来描述↓↓↓

size[u]	保存以u为根的子树节点个数
top[u]	保存当前节点所在链的顶端节点
son[u]	保存重儿子
dep[u]	保存结点u的深度值
fa[u]	保存结点u的父亲节点
tid[u]	保存树中每个节点剖分以后的新编号（DFS的执行顺序）
rnk[u]	保存当前节点在树中的位置

 

二.操作

算法大致需要进行两次的DFS，第一次dfs：记录所有的重边，第二次dfs：连重边成重链；

第一次：

得到当前节点的父亲结点（fa数组）、当前结点的深度值（dep数组）；

当前结点的子结点数量（size数组）、当前结点的重儿子（son数组）；

void dfs1(int u)
{
	size[u]=1;
	for(int i=head[u];~i;i=e[i].start)
	{
		int v=e[i].end;
		if(v==fa[u]) continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		size[u]+=size[v];
		if(size[v]>size[son[u]]) son[u]=v;
	}
}

第二次DFS的时候则可以将各个重结点连接成重链，轻节点连接成轻链;

并且将重链（其实就是一段区间）用数据结构（一般是树状数组或线段树）来进行维护，并且为每个节点进行编号;

其实就是DFS在执行时的顺序（tid数组），以及当前节点所在链的起点（top数组），还有当前节点在树中的位置（rank数组）。

void dfs2(int u,int now)
{
	top[u]=now;
	rak[u]=++id;
	dfn[id]=u;
	if(!son[u]) return ;
	dfs2(son[u],now);
	for(int i=head[u];~i;i=e[i].start)
	{
		int v=e[i].end;
		if(v!=son[u] && v!=fa[u])
		{
			dfs2(v,v);
		}
	}
}

而操作修改和查询，则以LibreOJ #139 树链剖分为例来讲
对于路径权值操作有：

• 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
• 询问路径：询问某条路径上节点的权值和。

void modify_path(int x,int y,LL add)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(fx,fy);
			swap(x,y);
		}
		T.update(1,n,1,rak[fx],rak[x],add);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	T.update(1,n,1,rak[x],rak[y],add);
}

LL query_path(int x,int y)
{
	LL res=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(fx,fy);
			swap(x,y);
		}
		res+=T.query(1,n,1,rak[fx],rak[x]);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res+=T.query(1,n,1,rak[x],rak[y]);
	return res;
}

而对于子树操作：

• 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
• 询问子树：询问某个子树内节点的权值和。

int check(int x)
{
	if(x==root)return -1;
	if(!(rak[x]<rak[root] && rak[x]+size[x]-1>=rak[root])) return 0;
	int now=root;
	while(dep[now]>dep[x])
	{
		if(fa[top[now]]==x)
			return top[now];
		now=fa[top[now]];
	}
	return son[x];//!!!!!!
}

void modify_tree(int x,LL y)
{
	int k=check(x);
	switch(k)
	{
		case -1:T.update(1,n,1,1,n,y);break;
		case 0:T.update(1,n,1,rak[x],rak[x]+size[x]-1,y);break;
		default:T.update(1,n,1,1,n,y);T.update(1,n,1,rak[k],rak[k]+size[k]-1,-y);break;
	}
}

LL query_tree(int x)
{
	LL res=0;
	int k=check(x);
	switch(k)
	{
		case -1:res=T.tree[1];break;
		case 0:res=T.query(1,n,1,rak[x],rak[x]+size[x]-1);break;
		default:res=T.tree[1]-T.query(1,n,1,rak[k],rak[k]+size[k]-1);break;
	}
	return res;
}

然后再用线段树维护一下就ok√

struct tre
{
	LL tree[maxn<<4],lazy[maxn<<4];
	
	void pushup(int rt)
	{
		tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	}

	void pushdown(int l,int r,int rt)
	{
		if(!lazy[rt]) return ;
		int mid=(l+r)>>1;
		tree[rt<<1]+=lazy[rt]*(mid-l+1);
		tree[rt<<1|1]+=lazy[rt]*(r-mid);
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		lazy[rt]=0;
	}
	
	void buildtree(int l,int r,int rt)
	{
		if(l==r)
		{
			tree[rt]=a[dfn[l]];
			return ;
		}
		int mid=(l+r)>>1;
		buildtree(lson);
		buildtree(rson);
		pushup(rt);
	}
	
	void update(int l,int r,int rt,int ql,int qr,LL add)
	{
		int len=r-l+1;
		if(ql<=l && qr>=r)
		{
			lazy[rt]+=add;
			tree[rt]+=len*add;
			return ;
		}
		int mid=(l+r)>>1;
		pushdown(l,r,rt);
		if(ql<=mid) update(lson,ql,qr,add);
		if(qr>mid) update(rson,ql,qr,add);
		pushup(rt);
	}

	LL query(int l,int r,int rt,int ql,int qr)
	{
		if(l>qr||r<ql)return 0;
		if(ql<=l && qr>=r)
		{
			return tree[rt];
		}
		int mid=(l+r)>>1;
		pushdown(l,r,rt);
		LL res=0;
		if(ql<=mid) res+=query(lson,ql,qr);
		if(qr>mid) res+=query(rson,ql,qr);
		return res;
	}
}T;

至此，代码已经轻松到了两百三十多行 姨母笑/
可以预见未来调试bug的悲惨情景了QAQ

三.实例

先从模板题开始啦，以后有时间再甩其他题上来otz

【 题目描述 】
给定一棵 nnn 个节点的树，初始时该树的根为 111 号节点，每个节点有一个给定的权值。下面依次进行 mmm 个操作，操作分为如下五种类型：

• 换根：将一个指定的节点设置为树的新根。
• 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
• 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
• 询问路径：询问某条路径上节点的权值和。
• 询问子树：询问某个子树内节点的权值和。

类型分别对应的是1,2,3,4,5；
输出：对于每一个类型为 4 或 5 的操作，输出一行一个整数表示答案.

解析：模板题，就不说其他的了QAQ

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<deque>
#include<cmath>
#include<cctype>
#define LL long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

using namespace std;

const int maxn=100000+7;

int n,m;
int a[maxn];
int id=0,root,tot=0;
int fa[maxn],dep[maxn];
int dfn[maxn],top[maxn];
int son[maxn],head[maxn];
int size[maxn],rak[maxn];

struct edge
{
	int start,end;
}e[maxn<<1];

int read()
{
	char c=getchar();int x=0,f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}

void addedge(int u,int v)
{
	e[++tot].end=v;
	e[tot].start=head[u];
	head[u]=tot;
}

struct tre
{
	LL tree[maxn<<4],lazy[maxn<<4];
	
	void pushup(int rt)
	{
		tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	}

	void pushdown(int l,int r,int rt)
	{
		if(!lazy[rt]) return ;
		int mid=(l+r)>>1;
		tree[rt<<1]+=lazy[rt]*(mid-l+1);
		tree[rt<<1|1]+=lazy[rt]*(r-mid);
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		lazy[rt]=0;
	}
	
	void buildtree(int l,int r,int rt)
	{
		if(l==r)
		{
			tree[rt]=a[dfn[l]];
			return ;
		}
		int mid=(l+r)>>1;
		buildtree(lson);
		buildtree(rson);
		pushup(rt);
	}
	
	void update(int l,int r,int rt,int ql,int qr,LL add)
	{
		int len=r-l+1;
		if(ql<=l && qr>=r)
		{
			lazy[rt]+=add;
			tree[rt]+=len*add;
			return ;
		}
		int mid=(l+r)>>1;
		pushdown(l,r,rt);
		if(ql<=mid) update(lson,ql,qr,add);
		if(qr>mid) update(rson,ql,qr,add);
		pushup(rt);
	}

	LL query(int l,int r,int rt,int ql,int qr)
	{
		if(l>qr||r<ql)return 0;
		if(ql<=l && qr>=r)
		{
			return tree[rt];
		}
		int mid=(l+r)>>1;
		pushdown(l,r,rt);
		LL res=0;
		if(ql<=mid) res+=query(lson,ql,qr);
		if(qr>mid) res+=query(rson,ql,qr);
		return res;
	}
}T;
//-----orz

void dfs1(int u)
{
	size[u]=1;
	for(int i=head[u];~i;i=e[i].start)
	{
		int v=e[i].end;
		if(v==fa[u]) continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		size[u]+=size[v];
		if(size[v]>size[son[u]]) son[u]=v;
	}
} 

void dfs2(int u,int now)
{
	top[u]=now;
	rak[u]=++id;
	dfn[id]=u;
	if(!son[u]) return ;
	dfs2(son[u],now);
	for(int i=head[u];~i;i=e[i].start)
	{
		int v=e[i].end;
		if(v!=son[u] && v!=fa[u])
		{
			dfs2(v,v);
		}
	}
}
//------QAQ

int check(int x)
{
	if(x==root)return -1;
	if(!(rak[x]<rak[root] && rak[x]+size[x]-1>=rak[root])) return 0;
	int now=root;
	while(dep[now]>dep[x])
	{
		if(fa[top[now]]==x)
			return top[now];
		now=fa[top[now]];
	}
	return son[x];//!!!!!!
}

void modify_path(int x,int y,LL add)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(fx,fy);
			swap(x,y);
		}
		T.update(1,n,1,rak[fx],rak[x],add);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	T.update(1,n,1,rak[x],rak[y],add);
}

LL query_path(int x,int y)
{
	LL res=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(fx,fy);
			swap(x,y);
		}
		res+=T.query(1,n,1,rak[fx],rak[x]);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res+=T.query(1,n,1,rak[x],rak[y]);
	return res;
}

void modify_tree(int x,LL y)
{
	int k=check(x);
	switch(k)
	{
		case -1:T.update(1,n,1,1,n,y);break;
		case 0:T.update(1,n,1,rak[x],rak[x]+size[x]-1,y);break;
		default:T.update(1,n,1,1,n,y);T.update(1,n,1,rak[k],rak[k]+size[k]-1,-y);break;
	}
}

LL query_tree(int x)
{
	LL res=0;
	int k=check(x);
	switch(k)
	{
		case -1:res=T.tree[1];break;
		case 0:res=T.query(1,n,1,rak[x],rak[x]+size[x]-1);break;
		default:res=T.tree[1]-T.query(1,n,1,rak[k],rak[k]+size[k]-1);break;
	}
	return res;
}
//------QAQ

int main()
{
	root=1;
	n=read();
	tot=0;
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=2;i<=n;i++)
	{
		int x=read();
		addedge(x,i);
		addedge(i,x);
	}
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	T.buildtree(1,n,1);
	m=read();
	while(m--)
	{
		int op=read();
		if(op==1)
		{
			int x=read();
			root=x;
		}
		else if(op==2)
		{
			int x=read(),y=read(),z=read();
			modify_path(x,y,z);
		}
		else if(op==3)
		{
			int x=read(),y=read();
			modify_tree(x,y);
		}
		else if(op==4)
		{
			int x=read(),y=read();
			printf("%lld\n",query_path(x,y));
		}
		else 
		{
			int x=read();
			printf("%lld\n",query_tree(x));
		}
	}

	return 0;
}

看吧，其实也没有多少，连三百行都没有到. 摊手/

蓝后下午再写orz，还有两道题