Lca的四种写法(4) 树链剖分

#LCA专题之转RMQ

LCA(Lowest Common Ancestors)即最近公共祖先。在图论中，我们往往需要解决一些树上的操作，而很多时候我们需要求出某两个结点的最近公共祖先

求LCA 我们前面用树上倍增讲到可以一起往上跳，而用树连剖分的方式也是往上跳，但是每次由该节点的链顶top较大的结点跳到该链的链顶top的父亲位置

什么是树链剖分呢，对于一棵树我们都可以将其每一个结点划分到一条链里，分为重链和轻链，对于每一个结点来说，他的所有子树中，结点数最多的那棵子树的根节点就是他的重儿子，其余儿子叫轻儿子 而从某一个点开始一直连重儿子直到叶节点，这样的一条链叫重链。

我们进行两遍dfs，

• 第一遍dfs1我们求出每个结点的父亲，深度，和每棵子树的大小，记录每个结点的重儿子。
• 第二遍dfs2我们求出每条链的顶端top，每个点的dfs序和dfs序对应的点（用于可以拿其他数据结构维护，求LCA没有必要）

用邻接表存图

struct Edges{
	int s,t,nxt;
	Edges(){
		s = t = nxt = 0;
	}
	Edges(int _s,int _t,int _nxt):s(_s),t(_t),nxt(_nxt){}
}e[M*2];
int tot = 1,head[N]；
inline void add(int s,int t){
	e[++tot] = Edges(s,t,head[s]);
	head[s] = tot;
	e[++tot] = Edges(t,s,head[t]);
	head[t] = tot;
}

第一次dfs

void dfs1(int u,int father,int d){
	dep[u] = d;
	fa[u] = father;
	siz[u] = 1;
	int v;
	for(int i=head[u];i;i = e[i].nxt){
		v = e[i].t;
		if(v == father) continue;
		dfs1(v,u,d+1);
		siz[u]+=siz[v];
		if(son[u] == 0 || siz[v]>siz[son[u]]) son[u] = v;
	}
}

第二次dfs

void dfs2(int u,int r){
	top[u] = r;
	//vis[u] = cnt;
	//rnk[cnt] = u;  // 设置dfs序号对应成当前结点
	if(son[u] == 0)return ;
	dfs2(son[u],r);
	int v;
	for(int i=head[u];i;i = e[i].nxt){
		v = e[i].t;
		if(v!=son[u] && v!=fa[u]){
			dfs2(v,v);
		}
	}
}

求lca时就是不断的往上跳

int lca(int u,int v){
	if(top[u] == top[v]) return dep[u]<dep[v]?u:v;
	for(;top[u]!=top[v];)
	if(dep[top[u]]<dep[top[v]]) 
		v = fa[top[v]];
	else u = fa[top[u]];
	return dep[u]<dep[v]?u:v;
}

这就是用树链剖分的方式求LCA

有空再配图