题解 P7103 【「C.E.L.U-01」族谱树】
无尽星空
·
·
题解
前言
看见题解有 树剖 求 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 上的询问（实际上就是这样的）.
其实就相当于 $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$ )
### 最后
上代码
###### ~~（可能这才是你最期待的）~~ ：
##### 代码真的挺短的
```cpp
#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;
}
```
##
### 感谢阅读