tg重点知识点：LCA

文件头

求LCA的基本方式：

1. 在线法

代表：倍增，rmq

这里介绍倍增法。

先预处理出每一个节点的 $2^k$ 级祖先以及深度。

求LCA时，先让两个节点深度相同，再从大到小枚举 $k$ ，如果 $x$ 的 $k$ 级祖先不等于 $y$ 的 $k$ 级祖先就往上跳。

因为我们跳的是LCA的下一层，所以要输出 $x$ 的 $0$ 级祖先。

核心代码：

vector<int> g[500001];
int n,q;
int depth[500001],f[500001][31];
void dfs(int x, int fa)
{
	depth[x]=depth[fa]+1;
	f[x][0]=fa;
	For(i,1,log2(depth[x])+1)
		f[x][i]=f[f[x][i-1]][i-1];
	For(i,0,g[x].size()-1)
		if(g[x][i]!=fa)
			dfs(g[x][i],x);
}
int lca(int x, int y)
{
	if(depth[y]<depth[x]) swap(y,x);
	while(depth[y]>depth[x]) y=f[y][(int)log2(depth[y]-depth[x])];
	if(x==y) return x;
	ForDown(k,log2(depth[y]),0)
	{
		if(f[x][k]!=f[y][k])
		{
			x=f[x][k],y=f[y][k];
		}
	}
	return f[x][0];
}
signed main()
{
	read(n,q);
	For(i,1,n-1)
	{
		int u,v;
		read(u,v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,1);
	//cout<<"wedrftgyhujikoswerdtfyguh"<<endl;
	while(q--)
	{
		int x,y;
		read(x,y);
		write_with_endl(lca(x,y));
	}
	return 0;
}

复杂度 $O(qlogn)$

2. 离线法

代表：tarjan

把所有询问存下来，然后在回溯时将并查集中当前节点的“父亲”设为它的父节点。然后如果有一个询问的两个点都算过了，从并查集中找结果存进来。最后输出。

核心代码：

int n,m,s;
struct Edge
{
    int v,nxt;
}query[1000001];
int head[500001],cnt=0;
vector<int> g[500001];
int lca[1000001];
void add(int x, int y)
{
    query[++cnt]=(Edge){y,head[x]};
    head[x]=cnt;
}

bool used[500001];
int f[500001];
int find(int x)
{
    return f[x]==x ? f[x] : f[x]=find(f[x]);
}
void tarjan(int x)
{
    used[x]=1;
    For(i,0,g[x].size()-1)
    {
        if(used[g[x][i]]) continue;
        tarjan(g[x][i]);
        f[g[x][i]]=x;
    }
    for(int i=head[x];i;i=query[i].nxt)
    {
        if(used[query[i].v])
        {
            lca[i%2+i]=find(query[i].v);
        }
    }
}

int main()
{
    read(n);read(m);read(s);
    For(i,1,n) f[i]=i;
    For(i,1,n-1)
    {
        int u,v;
        read(u);read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    For(i,1,m)
    {
        int u,v;
        read(u);read(v);
        add(u,v);
        add(v,u);
    }
    tarjan(s);
    For(i,1,m)
    {
        write(lca[2*i]);
        putchar('\n');
    }
    return0;
}

复杂度 $O(n)$。