树剖求lca

算法分析

用于求lca较广泛的算法大概就是倍增了，但倍增的常数较大，遇到一些毒

瘤的题往往会被卡掉，这时，学会用树剖求lca就变得十分重要

利用树剖求lca，我们首先需要对树进行剖分，剖分的方式任选，在这里我

采取轻重链剖分，剖分完后，在询问两个点的lca，先判断两个点是否在同一

重链上，假设在同一重链，此时深度较小的就是lca,假设不在同一重链

我们对深度较大的点向上跳，跳到链顶的父亲，实现跨链操作，直到两点

达到同一重链

每次查询的时间复杂度为(O(long n))的

现在还是不清楚为什么按洛谷模板题的数据范围那么诡异

按数据范围开反而炸了

放代码吧

这道题是洛谷的模板题

这里

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=5e6+10;
int n,m,s,l;
inline int read(){
	int ret=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		ret=ret*10+(ch^'0');
		ch=getchar();
	}
	return ret*f;
}
struct node{
	int nex;
	int to;
}e[maxn];
int cnt;
int head[maxn];
int deep[maxn];
void add(int u,int v){
	cnt++;
	e[cnt].nex=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
int son[maxn];
int size[maxn];
int fa[maxn];
void dfs1(int x){
	deep[x]=deep[fa[x]]+1;
	size[x]=1;
	for(int i=head[x];i;i=e[i].nex){
		int y=e[i].to;
		if(y!=fa[x]){
			fa[y]=x;
			dfs1(y);
			size[x]+=size[y];
			if(size[son[x]]<size[y]){
				son[x]=y;//find the heavlial son
			}
		} 
	}
	return ;
}
int top[maxn];
void dfs2(int x){
	if(x==son[fa[x]]){
		top[x]=top[fa[x]];
	}
	else 
		top[x]=x;
	for(int i=head[x];i;i=e[i].nex){
		int y=e[i].to;
		if(fa[y]==x){
			dfs2(y);
		}
	}
	return ;
}
void pre(int x){
	dfs1(x);
	dfs2(x);
	return ;
}
int query(int u,int v){
    while(top[u]!=top[v])
    {
        if(deep[top[u]]>deep[top[v]])
            u=fa[top[u]];
        else
            v=fa[top[v]];
    }
    if(deep[u]<deep[v])
        return u;
    return v;
}
int main(){
//	freopen("a.in","r",stdin);
	n=read();
	m=read();
	s=read();
	int x,y;
	for(int i=1;i<=n-1;i++){
		x=read();
		y=read();
		add(x,y);
		add(y,x);
	}
	pre(s);
	for(int i=1;i<=m;i++){
		x=read();
		y=read();
		cout<<query(x,y)<<endl;
	}
	return 0;
}