题解：CF208E - 洛谷保存站

# CF208E 题解
这里提供一个比较劣的做法。

对于每次询问，求出 $x$ 的 $p$ 级表亲 $t$，则答案为 $t$ 的子树内与 $x$ 同深度的节点个数 $-1$。我们知道，一棵子树内的 dfs 序是连续的，考虑把询问拍成序列，用莫队处理。

时间复杂度：$\Theta(m\sqrt{n})$。

代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,K=4e2+5;
int n,fa[N],m,dp[N][20],lg[N],t,l[K],r[K],pos[N],dfn[N],siz[N],ans[N],cnt,c[N],dep[N],rnk[N];
struct ask{
	int l,r,v,id;
	bool operator<(const ask&_)const{
		return (pos[l]==pos[_.l]?(r==_.r?0:r<_.r):l<_.l);
	}
}q[N];
vector<int>v[N];
void dfs(int cur){
	dfn[cur]=++cnt,rnk[cnt]=cur,siz[cur]=1,dp[cur][0]=fa[cur],dep[cur]=dep[fa[cur]]+1;
	for(int i=1;i<=lg[dep[cur]];i++)dp[cur][i]=dp[dp[cur][i-1]][i-1];
	for(int to:v[cur])dfs(to),siz[cur]+=siz[to];
}
void add(int x){c[dep[rnk[x]]]++;}
void del(int x){c[dep[rnk[x]]]--;}
int main(){
	cin>>n;
	lg[0]=-1;
	for(int i=1;i<=n;i++){
		cin>>fa[i];
		if(fa[i])v[fa[i]].push_back(i);
		lg[i]=lg[i>>1]+1;
	}
	for(int i=1;i<=n;i++)if(!fa[i])dfs(i);
	int t=sqrt(n);
	for(int i=1;i<=t;i++)l[i]=r[i-1]+1,r[i]=i*t;
	if(r[t]<n)t++,l[t]=r[t-1]+1,r[t]=n;
	for(int i=1;i<=t;i++)for(int j=l[i];j<=r[i];j++)pos[j]=i;
	cin>>m;
	cnt=0;
	for(int i=1;i<=m;i++){
		int x,l;
		cin>>x>>l;
		if(l>=dep[x])continue;
		cnt++;
		q[cnt].v=dep[x];
		while(l)x=dp[x][lg[l]],l-=(1<<lg[l]);
		q[cnt].l=dfn[x],q[cnt].r=dfn[x]+siz[x]-1,q[cnt].id=i;
	}
	sort(q+1,q+cnt+1);
	int l=1,r=0;
	for(int i=1;i<=cnt;i++){
		while(l>q[i].l)add(--l);
		while(r<q[i].r)add(++r);
		while(l<q[i].l)del(l++);
		while(r>q[i].r)del(r--);
		ans[q[i].id]=c[q[i].v]-1;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
	return 0;
}
```

正在渲染内容...