树链剖分

把一棵树剖分成若干条链，然后对链进行操作，维护路径上的信息。

有点像分块，也是暴力做法，单个操作太慢就整个操作。

我们一般用 重链剖分 ，也就是根据子树大小把边分成轻重边。

重链剖分

定义

重儿子：所有子节点中子树最大的节点，多个一样的取任意。

轻儿子：不是重儿子的就是轻儿子。

重边：从该节点到重儿子的边。

轻边：从该节点到轻儿子的边。

重链：重边首尾相连组成的链。

性质

1. 剖分时我们先遍历重儿子，最终 \(dfs\) 序压树，出来的区间重链的区间是连续的。

2. 任意一个节点到根节点最多走 \(O(logN)\) 条重链，
   所以任意两个节点之间的路径最多包含 \(O(2log(N))\) 条重链
   （感性证明：每次分轻重链都会把子树分成两半，最多 \(log_2N\) 条，两个节点之间的路可以看成两条到根的路）

（很清楚的一张图）

实现

维护的值(一下变量名为个人习惯命名)

\(dfs\) 两次，第一次找 \(son\)，维护\(sz,dep,fa\),找出重儿子。

第二次更新 \(top,dfn,rk\)，记录 \(dfs\)序。

int son[N],fa[N],sz[N],dep[N],rk[N],dfn[N],cnt,top[N];
void dfs1(int u,int f)
{
	son[u]=-1; sz[u]=1; dep[u]=dep[f]+1; fa[u]=f;
	for(int i=head[u];i;i=e[i].u)
	{
		int v=e[i].v;
		if(v==f) continue; 
		dfs1(v,u); sz[u]+=sz[v];
    	//a[v]=e[i].w; 边权改点权
		if(son[u]==-1||sz[son[u]]<sz[v]) son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t; dfn[u]=++cnt; rk[cnt]=u;
	if(son[u]==-1) return; dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].u)
	{
		int v=e[i].v;
		if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
	}
}//dfs

查询及修改

有点像 lca ，凭借重链往上跳，同时进行区间操作。

void mdfpath(int x,int y,int v)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		mdf(1,dfn[top[x]],dfn[x],v);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	mdf(1,dfn[x],dfn[y],v);//边权这里dfn[x]+1
}

int quepath(int x,int y)
{
	int res=0;
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res+=quesum(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res+=quesum(1,dfn[x],dfn[y]);//边权这里dfn[x]+1
	return res;
}

(码量主要在线段树，也可以用树状数组)

应用

树上路径问题转化为区间问题。