自动搬运

查看原文

来自洛谷，原作者为

	无尽星空 退役三年的老东西一个了

搬运于2025-08-24 22:26:39，当前版本为作者最后更新于2020-11-27 18:56:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

看见题解有 树剖 求 $LCA$ 过了加强的数据.

惊了，树剖 $(pao)$ 不是 $O(n log^2n)$ 吗？这是多么强悍的卡常大佬啊！

这里介绍一种代码短的板子做法.

正文

看见这题，第一眼想到了 $Tarjan$ 求 $LCA$ ( $Tarjan$ 老人家 $tql$ ).

没错，就是 $Tarjan$ .

void add(int x,int y)  {e[++cnt].to=y;e[cnt].nx=h[x];h[x]=cnt;}
void qadd(int x,int y)  {qe[++qcnt].to=y;qe[qcnt].nx=qh[x];qh[x]=qcnt;}
int find(int p)  {return fa[p]==p?p:fa[p]=find(fa[p]);}
void tarjan(int x)
{
	vis[x]=1;
	for(int i=h[x];i;i=e[i].nx)
	{
		int u=e[i].to;
		if(vis[u])  continue;
		tarjan(u);fa[u]=x;
	}
	for(int i=qh[x];i;i=qe[i].nx)
	{
		int u=qe[i].to;
		if(vis[u])  lct[(i&1?(i+1):(i-1))]=lct[i]=find(u);
	}
}

就是这个 $Tarjan$ ！

不会 $Tarjan$ 求 $LCA$ 的同志请 出门左转（不要看背景）.

但是 $Tarjan$ 是离线的，如果是 $Tarjan$ 可能无法处理（假如有三个深度为 $k$ 的点，最暴力的做法需要先求第一和第二个点的 $LCA$，再求 $LCA$ 和第三个点的 $LCA$）这样动态的询问.

似乎倍增可以应对动态询问，但妥妥 $TLE$ 到飞起（ 这题必须 $O(n+q)$ 呢 ），所以我们坚持 $Tarjan$ .

注意到 $Tarjan$ 求 $LCA$ 需要在要求 $LCA$ 的点上挂询问，那么，我们不妨开一个数组 $ans$，设当前点为 $x$ ，深度为 $d[x]$ ，则 $ans[d[x]]$ 表示处理到 $x$ 点之前所有深度为 $d[x]$ 的点的 $LCA$ , 那么这个数组就可以近似地认为是挂在点 $x$ 上的询问（实际上就是这样的）.

$dfs$ 到 $x$ 点时，若 $ans[d[x]]=0$ (之前没有深度为 $d[x]$ 的点），就令 $ans[d[x]]=x$ ，否则就像 $Tarjan$ 求 $LCA$ 一样令 $ans[d[x]]=find(ans[d[x]])$ .

其实就相当于 $Tarjan$ 求 $LCA$ 中的 $lct[i]=find(u)$ 这句：

for(int i=qh[x];i;i=qe[i].nx)
{
	int u=qe[i].to;
	if(vis[u])  lct[(i&1?(i+1):(i-1))]=lct[i]=find(u);
}

最后 $ans$ 数组存的就是答案 ( $ans[i]$ 就是所有深度为 $i$ 的点的 $LCA$ )

最后

上代码

（可能这才是你最期待的） ：

代码真的挺短的

#include<bits/stdc++.h>
#define R register int
using namespace std;
const int N=5e6+5;
int n,d[N],to[N],nx[N],h[N],fa[N],q,in,ans[N];
inline int read()//快读就不用说了吧
{
	int s=0;char c=getchar();
	while(!isdigit(c))  c=getchar();
	while(isdigit(c))  s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s;
}
int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}//并查集
void dfs(int x,int f)
{
	d[x]=d[f]+1;
	for(R i=h[x];i;i=nx[i])  dfs(to[i],x),fa[to[i]]=x;//tarjan 求LCA的合并
	ans[d[x]]=ans[d[x]]?find(ans[d[x]]):x;//核心部分，tarjan求LCA中的求答案部分
}
int main()
{
	n=read();q=read();
	for(R i=1;i<=n;i++)  fa[i]=i,in=read(),to[i]=i,nx[i]=h[in],h[in]=i;//读入+加边+并查集init
	dfs(1,0);
	while(q--)  printf("%d\n",ans[read()]);//O(1) 处理询问
	return 0;
}

感谢阅读