【模板】最近公共祖先(LCA)

题目

P3379
注：ybtoj问的是两点距离，即 d r o o t , x + d r o o t , y − 2 ∗ d r o o t , l c a ( x , y ) d_{root,x}+d_{root,y}-2*d_{root,lca(x,y)} droot,x​+droot,y​−2∗droot,lca(x,y)​

---

解析

关于LCA问题，目前有四种解法：
树剖 O ( n + q log ⁡ n ) O(n+q\log n) O(n+qlogn) 在线
倍增 O ( ( n + q ) log ⁡ n ) O((n+q)\log n) O((n+q)logn) 在线
ST O ( n log ⁡ n + q ) O(n\log n+q) O(nlogn+q) 在线
tarjan O ( n + q ) O(n+q) O(n+q) 离线
当然，它们都不支持修改树
本人只学会了倍增和tarjan，锅以后再补
先说最基础的倍增：
倍增的想法基于这样一点：n次向上移动(即向上标记法)可以用像快速幂一样的做法预处理出 f a 2 0 , f a 2 1 . . . f a 2 log ⁡ n fa_{2^0},fa_{2^1}...fa_{2^{\log n}} fa20​,fa21​...fa2logn​，就可以实现单次 O ( log ⁡ n ) O(\log n) O(logn)的查询

code(洛谷667ms):

#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
inline void write(int x)
{
	int F[20];
	int tmp=x>0?x:-x;
	if(x<0)putchar('-');
	int cnt=0;
	while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
	while(cnt>0)putchar(F[--cnt]);
	if(x==0)putchar('0');
	putchar('\n');
}
int n,m,s,head[500010],tot=0,nxt[1000010],to[1000010],dep[500010],lca[500010][20],x,y,k,mx=1;
void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
queue <int> a;
bool u[500010];
void bfs()
{
	while(!a.empty())
	{
		k=a.front(),a.pop();
		if(a.empty()&&nxt[head[k]]==0)mx=dep[k];
		for(int i=head[k];i;i=nxt[i])
		{
			if(!u[to[i]])
			{
				u[to[i]]=1;
				a.push(to[i]);
				lca[to[i]][0]=k;
				dep[to[i]]=dep[k]+1;
			}
		}
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])x^=y^=x^=y;
	int len=dep[x]-dep[y],k,s;
	while(len)
	{
		k=len&-len;
		len^=k;
		s=0,k>>=1;
		while(k)k>>=1,++s;
		x=lca[x][s];
	}
	if(x==y)return x;
	for(int i=log2(dep[x]);i>=0;--i)if(lca[x][i]!=lca[y][i])x=lca[x][i],y=lca[y][i];
	return lca[x][0];
}
int main()
{
	n=read(),m=read(),s=read();
	dep[s]=1;
	for(int i=1;i<n;i++)x=read(),y=read(),add(x,y),add(y,x);
	a.push(s),u[s]=1;
	bfs();
	for(int i=1;i<=log2(mx);i++)for(int j=1;j<=n;j++)if((1<<i)<dep[j])lca[j][i]=lca[lca[j][i-1]][i-1];
	while(m--)
	{
		x=read(),y=read();
		write(LCA(x,y));
	}
	return 0;
}

code(ybtoj156ms):

#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
inline void write(int x)
{
	int F[20];
	int tmp=x>0?x:-x;
	if(x<0)putchar('-');
	int cnt=0;
	while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
	while(cnt>0)putchar(F[--cnt]);
	if(x==0)putchar('0');
	putchar('\n');
}
int n,m,s,head[10010],dis[10010],tot=0,nxt[40010],to[40010],w[40010],z,dep[10010],lca[10010][16],x,y,k,mx=1;
void add(int x,int y,int z){to[++tot]=y,w[tot]=z,nxt[tot]=head[x],head[x]=tot;}
queue <int> a;
bool u[10010];
void bfs()
{
	while(!a.empty())
	{
		k=a.front(),a.pop();
		if(a.empty()&&nxt[head[k]]==0)mx=dep[k];
		for(int i=head[k];i;i=nxt[i])
		{
			if(!u[to[i]])
			{
				u[to[i]]=1,dis[to[i]]=w[i]+dis[k];
				a.push(to[i]);
				lca[to[i]][0]=k;
				dep[to[i]]=dep[k]+1;
			}
		}
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])x^=y^=x^=y;
	int len=dep[x]-dep[y],k,s;
	while(len)
	{
		k=len&-len;
		len^=k;
		s=0,k>>=1;
		while(k)k>>=1,++s;
		x=lca[x][s];
	}
	if(x==y)return x;
	for(int i=log2(dep[x]);i>=0;--i)if(lca[x][i]!=lca[y][i])x=lca[x][i],y=lca[y][i];
	return lca[x][0];
}
int main()
{
	n=read(),m=read(),s=1;
	dep[s]=1;
	for(int i=1;i<n;i++)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
	a.push(s),u[s]=1;
	bfs();
	for(int i=1;i<=log2(mx);i++)for(int j=1;j<=n;j++)if((1<<i)<dep[j])lca[j][i]=lca[lca[j][i-1]][i-1];
	while(m--)
	{
		x=read(),y=read();
		write(dis[x]+dis[y]-(dis[LCA(x,y)]<<1));
	}
	return 0;
}

再说tarjan：
众所周知，并查集有一个优化叫路径压缩，即优化询问
那么我们就考虑对向上标记法进行优化：
维护一个并查集，初始指向自己，并给每个节点一个状态type：
未递归的节点type=0
正在递归的节点type=1
递归结束的节点type=2
当一个节点递归结束，type=2时，将它合并到父节点
当搜索到与当前节点有关的一个询问时，考虑另一点是否type=2，若是，则答案即为另一点的get返回的结果
ybtoj没做，懒得再交一遍
神奇的是我线性跑得比倍增还慢(vector快出来背锅)

code(洛谷1.06s):

#include<cstdio>
#include<vector>
#define mp make_pair
using namespace std;
int n,m,root,head[500010],to[1000010],nxt[1000010],ans[500010],fa[500010],tot,x,y;
inline void add(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
vector<pair<int,int> > ask[500010];
bool ch[500010],vis[500010];
inline int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
inline void LCA(int x,int f)
{
	for(int i=head[x];i;i=nxt[i])if(to[i]!=f&&!vis[to[i]])LCA(to[i],x),fa[find(to[i])]=find(x),vis[to[i]]=1;
	for(int i=0;i<ask[x].size();++i)if((!ch[ask[x][i].second])&&vis[ask[x][i].first])ans[ask[x][i].second]=find(ask[x][i].first),ch[ask[x][i].second]=1;
}
int main()
{
	scanf("%d%d%d",&n,&m,&root),fa[n]=n;
	for(int i=1;i<n;++i)scanf("%d%d",&x,&y),add(x,y),add(y,x),fa[i]=i;
	for(int i=1;i<=m;++i){scanf("%d%d",&x,&y);if(x!=y)ask[x].push_back(mp(y,i)),ask[y].push_back(mp(x,i));else ans[i]=x;}
	LCA(root,0);
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}