Blood Cousins
前置知识：线段树合并。
我们先把题目转化一下。这里先设 \(v\) 的 \(p\) 级祖先为 \(u\)，事实上要求的东西就是 \(u\) 的 \(p\) 级后代的个数减 \(1\)，减 \(1\) 是因为要把自己减去。显然这个目标点 \(t\) 要满足两个要求：
-
\(t\) 在 \(u\) 子树内。
-
设 \(dep_u\) 表示 \(u\) 的深度，则 \(dep_u+p=dep_t\)。
于是我们对每个点建一棵权值线段树，维护深度，然后把询问离线下来，如果这个点有询问，我们就在合并后的权值线段树内查找目标深度的点的个数即可。
然后就说完了，直接看一下代码：
#include<bits/stdc++.h>
#define int long long
#define N 100005
#define M 200005
#define K 23
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int n,m,tot;
int h[N],e[M],ne[M],idx;
int fa[N][K],dep[N],res[N],rt[N];
vector<int>root;
vector<pii>ask[N];
void add(int a,int b){
e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;i<K;i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==f)continue;
dfs1(j,u);
}
}
int get(int u,int k){
for(int i=K-1;~i;i--){
if(k>>i&1){
u=fa[u][i];
}
}
return u;
}
struct node{
int l,r,sum;
}tr[N<<5];
void pushup(int u){
tr[u].sum=tr[tr[u].l].sum+tr[tr[u].r].sum;
}
void modify(int &u,int l,int r,int p){
if(!u)u=++tot;
if(l==r){
tr[u].sum++;
return;
}
int mid=l+r>>1;
if(p<=mid)modify(tr[u].l,l,mid,p);
else modify(tr[u].r,mid+1,r,p);
pushup(u);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
if(l==r){
tr[x].sum+=tr[y].sum;
return x;
}
int mid=l+r>>1;
tr[x].l=merge(tr[x].l,tr[y].l,l,mid);
tr[x].r=merge(tr[x].r,tr[y].r,mid+1,r);
pushup(x);
return x;
}
int qry(int u,int l,int r,int p){
if(l==r)return tr[u].sum;
int mid=l+r>>1;
if(p<=mid)return qry(tr[u].l,l,mid,p);
else return qry(tr[u].r,mid+1,r,p);
}
void dfs2(int u){
modify(rt[u],1,n,dep[u]);
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa[u][0])continue;
dfs2(j);
rt[u]=merge(rt[u],rt[j],1,n);
}
for(auto eu:ask[u]){
res[eu.y]=qry(rt[u],1,n,eu.x)-1;
}
}
signed main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int x;
cin>>x;
if(x)add(x,i),add(i,x);
else root.push_back(i);
}
for(auto i:root){
dep[i]=1;
dfs1(i,0);
}
cin>>m;
for(int i=1;i<=m;i++){
int x,k;
cin>>x>>k;
int p=get(x,k);
if(p==0){
res[i]=0;
continue;
}
ask[p].push_back({k+dep[p],i});
}
for(auto i:root){
dfs2(i);
}
for(int i=1;i<=m;i++){
cout<<res[i]<<' ';
}
return 0;
}