LCA（最近公共祖先）板子

因为求LCA的大多数是在线的算法，所以塔尖就不是很爽了，但是在离线的时候，塔尖很优的QAQ，在这里就先放一下倍增的LCA板子

#include<bits/stdc++.h>
using namespace std;
const int size=200100;
int f[size][20],d[size],dist[size];
int ver[2*size],edge[2*size],ne[2*size],head[2*size];
int T,n,m,tot=0,t;
int a[size];
queue<int>q;
void add(int x,int y,int z)
{
	ver[++tot]=y;
	edge[tot]=z;
	ne[tot]=head[x];
	head[x]=tot;
}
void bfs()
{
	q.push(1);
	d[1]=1;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=ne[i])
		{
			int y=ver[i];
			if(d[y])
			continue;
			d[y]=d[x]+1;
			dist[y]=dist[x]+edge[i];
			f[y][0]=x;
			for(int j=1;j<=t;j++)
			{
				f[y][j]=f[f[y][j-1]][j-1];
			}
			q.push(y);
		}
	}
}
int lca(int x,int y)
{
	if(d[x]>d[y])
	swap(x,y);
	for(int i=t;i>=0;i--)
	if(d[f[y][i]]>=d[x])
	y=f[y][i];
	if(x==y)
	return x;
	for(int i=t;i>=0;i--)
	if(f[x][i]!=f[y][i])
	{
		x=f[x][i];
		y=f[y][i];
	}
	return f[x][0];
}
int main()
{
	freopen("legendary.in","r",stdin);
	freopen("legendary.out","w",stdout);
	scanf("%d",&n);
	t=(int)(log(n)/log(2))+1;
	for(int i=1;i<=n;i++)
	head[i]=d[i]=0;
	tot=0;
	a[1]=1;
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		a[i]=i;
		add(i,x,1);
		add(x,i,1);
	}
	bfs();
	for(int i=2;i<=n;i++)
	{
		printf("%d\n",dist[a[i]]+dist[a[i-1]]-2*dist[lca(a[i],a[i-1])]);
	}
	return 0;
}
/*
10
1
1
3
1
2
3
6
1
8
*/

板子代码出自蓝书QAQ

推荐博客

https://www.luogu.org/blog/cccx2016/solution-p3379

dfs的模板

#include<bits/stdc++.h>
using namespace std;
const int oi=500010;
int head[oi*2],ne[oi*2],ver[oi*2],tot=0;
int lg[oi],f[oi][22],deep[oi];
int n,m;
void add(int x,int y)
{
    ver[++tot]=y;
    ne[tot]=head[x];
    head[x]=tot;
}
int dfs(int x,int y)
{
    deep[x]=deep[y]+1;
    f[x][0]=y;
    for(int i=1;(1<<i)<=deep[x];i++)
    {
        f[x][i]=f[f[x][i-1]][i-1];
    }
    for(int i=head[x];i;i=ne[i])
    {
        if(ver[i]==y)
        continue;
        dfs(ver[i],x);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])
    swap(x,y);
    while(deep[x]>deep[y])
    {
        x=f[x][lg[deep[x]-deep[y]]-1];
    }
    if(x==y)
    return x;
    for(int i=lg[deep[x]]-1;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<=m;i++)
    {
        int maxx1=0,maxx2=0;
        int x,y,z,zu1,zu2,zu3,d1,d2,d3;
        scanf("%d%d%d",&x,&y,&z);
        zu1=lca(x,y);d1=deep[x]+deep[y]-deep[zu1]+(deep[z]-2*deep[lca(z,zu1)]);
        zu2=lca(x,z);d2=deep[x]+deep[z]-deep[zu2]+(deep[y]-2*deep[lca(y,zu2)]);
        zu3=lca(y,z);d3=deep[y]+deep[z]-deep[zu3]+(deep[x]-2*deep[lca(x,zu3)]);
        // cout<<zu1<<' '<<zu2<<' '<<zu3<<endl;
        // cout<<d1<<' '<<d2<<' '<<d3<<endl;
        maxx1=d1;
        maxx2=zu1;
        if(d2<maxx1)
        {
            maxx1=d2;
            maxx2=zu2;
        }
        if(d3<maxx1)
        {
            maxx1=d3;
            maxx2=zu3;
        }
        printf("%d %d\n",maxx2,maxx1);
    }
}