浅谈树链剖分（上）

本文极其适合包括刚刚学完树的定义的OIer在内的OIer。~~是人都能看懂。~~

例题：

[P3379 LCA](https://www.luogu.com.cn/problem/P3379)

虽然说树链剖分和LCA没啥关系，正式比赛时大家也多用倍增算法为主，但是在这里算是一个引子吧。

LCA，最近公共祖先，即两个点之间深度最大~~最亲民~~的公共祖先。比如这么一棵树：

```
father[2]=4
father[1]=4
father[3]=1
father[5]=1
```
（`father`表示一个节点的父亲节点编号。）我们假设$de_x$是$x$节点的深度，$LCA(x,y)$是$x$,$y$两个节点的最近公共祖先。如果$de_x>de_y$，那么$LCA(x,y)=LCA(Father_x,y)$，反之亦然。如果$de_x=de_y$的话，$LCA(x,y)=LCA(Father_x,Father_y)$。接下来我们就可以有一份TLEcode了：
```cpp
int LCA(int a,int b){
	while(a!=b){
		if(de[a]<de[b]){//将a设为深度较小的那个
			swap(a,b);
		}
		a=fa[a];//a往上跳
	}
	return a;
}
```
这个思路很显然不是最优的。~~事实上，它非常烂。~~
它的时间复杂度最坏是$O(nm)$。我们来分析一下它的缺点。每一操作后，它都只能跳一条边。**如果我们可以把树拆成多条链，每次跳到链顶节点的父亲节点，就可以避免大量的重复操作。**
但是我在这里提醒一下大家，此时每次跳跃过程中我们操作的是其中**链顶节点的深度较大的那一个**，而不是当前节点。

code:
```cpp
void dfs(int x,int tp){//x表示当前dfs到的节点，tp表示该节点所在链的顶端节点编号
    de[x]=de[fa[x]]+1;
    top[x]=tp;
    int flag=0;
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]){
            int v=g[x][i];
            fa[v]=x;
            if(flag==1){//不是第一个点
                dfs(v,v);//从这个点开始新建一条链
            }else{//是第一个点
                flag=1;
                dfs(v,tp);//和原来的节点并入同一条链
            }
        }
    }
}
int LCA(int a,int b){
	while(top[a]!=top[b]){//只要不在同一条链上
		if(de[top[a]]<de[top[b]]){//注意！比较所在链顶部节点的深度
			swap(a,b);
		}
		a=fa[top[a]];//先跳一条链，再跳一条边
	}
	if(de[a]<de[b])swap(a,b);//返回其深度较小的
	return b;
}
```
这个代码时间复杂度仍然是$O(nm)$。举个例子吧，比如以下毒瘤数据：
```
root=1
father[2]=1
father[3]=1
father[4]=3
father[5]=3
father[6]=5
father[7]=5
…………
father[2*i]=2*i-1
father[2*i+1]=2*i-1
```
对于以上情况，我们会惊奇的发现，每一条链长度只有2！如果我们从节点$500000$开始跳跃，需要跳跃大约$500000$次！如何才能使跳跃次数足够小呢？

假设跳跃前节点为$x$，跳跃后节点为$y$，如果以$y$为根的子树的大小（以下简称$sze_y$）是$sze_x$的两倍甚至更多，那么即使从$x$跳到根（$root$）也不过跳跃$log_{2}n$次。为了满足这一条件，我们可以对上面的剖分方式进行修改：**如果$2sze_x<sez_{father_x}$，那么就不计入一条链；否则计入一条。**
另外，我们还可以对该规则简化：**如果$x$是$father_x$当中$sze_x$最大的子节点，那么该节点被称为$father_x$的重儿子并与$father_x$计入一条链。**

AC code:
```cpp
#include<iostream>
#include<vector>
using namespace std;
vector<int>g[500005];
int de[500005],fa[500005],top[500005],sze[500005],son[500005];
void dfs(int x){
    de[x]=de[fa[x]]+1;
    sze[x]=1;//注意！节点本身也算入
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]){
            int v=g[x][i];
            fa[v]=x;
            dfs(v);
            sze[x]+=sze[v];//记录子树大小
            if(sze[v]>sze[son[x]]){
                son[x]=v;//处理重儿子
            }
        }
    }
}
void dfs2(int x,int tp){
    if(x==0)return;//防止重儿子为0
    top[x]=tp;
    dfs2(son[x],tp);//计入同一链
    for(int i=0;i<g[x].size();i++){
        if(g[x][i]!=fa[x]&&g[x][i]!=son[x]){
            int v=g[x][i];
            dfs2(v,v);
        }
    }
}
int LCA(int a,int b){
	while(top[a]!=top[b]){
		if(de[top[a]]<de[top[b]]){
			swap(a,b);
		}
		a=fa[top[a]];
	}
	if(de[a]<de[b])swap(a,b);
	return b;
}
int main(){
	int n,q,r;
	cin>>n>>q>>r;
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(r);
	dfs2(r,r);//dfs两遍
	for(int i=0;i<q;i++){
		int x,y;
		cin>>x>>y;
		cout<<LCA(x,y)<<endl;
	}
	return 0;
}
```
时间复杂度分析：

$DFS$：$O(n)$

$LCA$：$O(logn)$

总时间复杂度：$O(n+mlogn)$（比倍增还优秀一点）

空间复杂度：$O(n)$（比倍增还优秀好多）

总结：本篇博客以LCA为引子简单介绍了树链剖分。若有不懂或不明白之处，欢迎提出。

正在渲染内容...