【学习笔记】树链剖分

一、重链剖分

1. 定义 & 作用

树链剖分用于解决在树上执行的操作，将树上操作变为区间操作。用区间来维护。

2. 主要思想 & 实现

有一棵树

然后，我们把边区分一下，有一些边是“重边”，其余的是“轻边”，像这样：（红边为重边，黑边为轻）

重边和轻边如何确定呢？看每一个结点旁的红色数字，代表他的子节点个数，每一个节点连向自己子节点最多的儿子的那条边即为重边了。

然后许多个连在一起的重边就组合在一起，被称为重链。重链的顶端为这条重链中深度最低的节点。实现的话，就把代码按上面的那样打就好了。只需要对于每一个节点，记录这个节点所在的重链的顶端。为 \(top_x\)。放上代码吧。

void cut(int x,int topx)
{
	id[x]=++fx;
	top[x]=topx;
	if(sons[x]==1)
	{
		ma[x]=id[x];
		return;
	}
	int maxi=0;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa[x])continue;
		if(sons[to]>sons[maxi])
			maxi=to;
	}
	cut(maxi,topx);
	ma[x]=max(ma[x],ma[maxi]);
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa[x]||to==maxi)
			continue;
		cut(to,to);
		ma[x]=max(ma[x],ma[to]);
	}
}

二、重链剖分的常见用途

1. 重链剖分求LCA

很简单。对于两个需要求 LCA 的节点，假设为 \(x\) 和 \(y\)，判断 \(top_x\) 和 \(top_y\) 哪个深度深，就把节点往上跳。即将这个节点设为自己 \(top\) 的父亲。反复执行，直到这两个节点在同一条重链上。

int lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])
        	a=fa[top[a]];
        else b=fa[top[b]];
    }
    if(dep[a]<dep[b]) return a;
    else return b;
}

2. 一些树上操作

我们根据重边先，轻边后的顺序遍历整棵树，以此打上编号，像这样：

蓝色数字为编号。这时可以发现一个东西，就是很多操作所涉及的所有结点都是连续的。比如说对自己子节点的操作......还有一些操作，是由一个个重链组成的，而每一条重链的编号是连续的，那可以开一个线段树，很多操作进行时，边跳（不断使得当前节点成为自己 \(top\) 的父亲）边改变节点们的值。详见模板 软件包管理器。