lca与树上（路径交、并，直径）问题

最近的一些比赛中经常用到树上$lca$的常见模型，整理一下：

首先整理一下$LCA$的四种求法：

1.倍增$LCA$：预处理$O(nlogn)$ 单次查询$O(logn)$

通过$bfs$预处理节点深度和$st$表倍增处理祖宗节点，在查询的时候用倍增先将两点跳到统一深度，再找同祖宗节点的最深节点

int n,depth[N],f[N][19];
vector<int>e[N];
void bfs(int root){
	memset(depth,0x3f,sizeof depth);
	depth[0]=0,depth[root]=1;//0为st表的哨兵
	queue<int>q;
	q.push(root);
	while(q.size()){
		int ver=q.front();
		q.pop();
		for(auto &to:e[ver]){
			if(depth[to]>depth[ver]+1){
				depth[to]=depth[ver]+1;
				f[to][0]=ver;
				for(int i=1;i<=18;i++)
				f[to][i]=f[f[to][i-1]][i-1];
			}
		}
	}
}
int lca(int a,int b){
	if(depth[a]<depth[b])swap(a,b);
	for(int i=18;i>=0;i--){
		if(depth[f[a][i]]<=depth[b])
		a=f[a][i];
	}
	if(a==b)return a;
	for(int i=18;i>=0;i--){
		if(f[a][i]!=f[b][i])
		a=f[a][i],b=f[b][i];
	}
	return f[a][0];
}

2.$Tarjan$离线$LCA$: 总体时间复杂度$O(n+q)$ ，$n$为节点 $q$为查询次数

暂定

3.在线$RMQLCA$：预处理$O(nlogn)$ 单次查询$O(1)$

通过$dfs$处理欧拉序及其深度，并保存每个节点第一次出现位置，通过$st$表维护区间深度最小值即可

int n,q,root,depth[N<<1],f[N<<1][19],se[N<<1],tot,Log[N<<1],id[N];
vector<int>e[N];
void dfs(int u,int d,int fa){
	se[++tot]=u;
	id[u]=tot;
	depth[tot]=d;
	for(auto &to:e[u]){
		if(to==fa)continue;
		dfs(to,d+1,u);
		se[++tot]=u;
		depth[tot]=d;
	}
}
int lca(int l,int r){
	int k=Log[r-l+1];
	return depth[f[l][k]]<depth[f[r-(1<<k)+1][k]]?
	se[f[l][k]]:se[f[r-(1<<k)+1][k]];
}
void solve(){
	cin>>n>>q>>root;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		e[u].pb(v);
		e[v].pb(u);
	}
	dfs(root,1,0);
	Log[1]=0,Log[2]=1;
	for(int i=3;i<=tot;i++)
	Log[i]=Log[i/2]+1;

	for(int i=1;i<=tot;i++)f[i][0]=i;

	for(int j=1;j<=Log[tot];j++)
	for(int i=1;i+(1<<j)-1<=tot;i++)
	if(depth[f[i][j-1]]<depth[f[i+(1<<(j-1))][j-1]])f[i][j]=f[i][j-1];
	else f[i][j]=f[i+(1<<(j-1))][j-1];
	
	while(q--){
		int u,v;cin>>u>>v;
		int l=id[u],r=id[v];
		if(l>r)swap(l,r);
	}
}

4.树链剖分$LCA$:预处理$O(n)$ 单次查询$O(logn)$

暂定

树上$LCA$的几种常用模型：

1.动态维护树的直径

2.树上路径的交

3.树上路径的并