链剖分

重链剖分

第一次 DFS 求重儿子（子节点更多的儿子）。

第二次 DFS 求重链剖分（先访问重儿子再访问其他轻儿子）。

变量：重儿子，子树大小，DFS 序（\(x\) 根子树 DFS 序中第一次出现位置），以 \(x\) 为根的子树的最后一次出现位置，深度，\(x\) 所在重链的顶端。

void dfs1(int x){//求出重儿子，sz[v] 最大的一个
	sz[x]=1;
	for(auto v:g[x]){
		if(v==fa[x])continue;
		dep[v]=dep[x]+1;//深度
		fa[v]=x;
		dfs1(v);
		sz[x]+=sz[v];
		if(sz[v]>sz[son[x]])som[x]=v;//大于当前重儿子
	}
}

/*
st[x] DFS 序（$x$ 根子树 DFS 序中第一次出现位置）
ed[x] 以 $x$ 为根的子树的最后一次出现位置
top[x] $x$ 所在重链的顶端
*/

void dfs2(int x){//求 dfs 序
	st[x]=ed[x]=++dc;
	if(!son[x])return;//叶子节点
	top[son[x]]=top[x];
	dfs2(son[x]);
	for(auto v:g[x]){
		if(v==fa[x]||v==son[x])continue;
		top[v]=v;
		dfs2(v);
	}
	ed[x]=dc;
}

性质：

一条重链上所有点在 DFS 序上连续；

任意点 \(x\) 到根的路径上经过的轻边数量不超过 \(log(n)\)。

求 LCA。

每次向上跳所在重链顶端较深的，直到 \(x,y\) 在同一条重链上，深度较浅的是 LCA。

轻儿子 \(top\) 等于自己。

int LCA(int x,int y){
	while(top[x]!=top[y]){//不在一条重链上
		if(dep[top[x]]<dep[top[y]])
			std::swap(x,y);//重链顶端更浅的
        x=fa[top[x]];
        //top[x] 一定是轻儿子
        //fa[top[x]] 重儿子，在重链上
        //fa[top[x]] 轻儿子，top[fa[top[x]]]=fa[top[x]]，再跳 fa 再跳过一个轻边
	}
	return dep[x]<dep[y]?x:y;
}

重链剖分模版：

支持操作：换根，修改路径权值，修改子树权值，询问路径或子树。

只需考虑子树，不用考虑 \(fa\) 和重链。