(Large atural) CF208E Blood Cousins / 原题链接
思路
这道题，我们可以考虑用 线段树合并 做。
首先，我们把询问离线存储起来，并且用倍增算法求出每个询问中，每个点的 (K) 辈祖先是谁。这样，题目就转化为了 “求某个点有多少个 (K) 辈儿子” 了，询问可以用链表或者 vector 存。
然后我们对于森林中的每一棵树分别考虑。假设某一个询问，转化后是求点 (A) 的 (K) 辈儿子数量，那我们只用求这棵树里有多少个点 (i) 使得 (dep_A+K=dep_i) 。因为只有 (A) 的子树中才会出现合法的点 (i) 。所以问题又转化为“某个点 (A) 的子树中有多少个点 (i) 使得 (dep_A+K=dep_i) ”。
所以我们可以进行 dfs ，给每一个点建立一个线段树，其中点 (o) 上建立的线段树中，节点 (l sim r) 代表点 (o) 子树中 (dep) 值为 (l sim r) 的点有多少个。故每遍历到一个点 (o)，先将 (dep_o) 插入线段树，然后与子树的线段树合并，最后依次查询它身上的询问。
代码
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
#define mar(o) for(int E=fst[o];E;E=e[E].nxt)
#define v e[E].to
#define lsn tre[ tre[o].lv ]
#define rsn tre[ tre[o].rv ]
using namespace std;
const int n7=101234,m7=201234,t7=4001234;
struct dino{int to,nxt;}e[m7];
struct elep{int l,r,lv,rv,val;}tre[t7];
struct galo{int o,ned;}qq[n7];
int n,T,ecnt,fst[n7],cnt,dep[n7],fc[n7][22],ans[n7],rot[n7],rotc;
vector <int> vec[n7];
void edge(int sta,int edn){
ecnt++;
e[ecnt]=(dino){edn,fst[sta]};
fst[sta]=ecnt;
}
void puhigh(int o){tre[o].val=lsn.val+rsn.val;}
void updat(int o,int num){
if(tre[o].l==tre[o].r){tre[o].val++;return;}
int mid=(tre[o].l+tre[o].r)>>1;
if(num<=mid){
if(!tre[o].lv){
cnt++,tre[o].lv=cnt;
tre[cnt]=(elep){tre[o].l,mid};
}
updat(tre[o].lv,num);
}
if(mid+1<=num){
if(!tre[o].rv){
cnt++,tre[o].rv=cnt;
tre[cnt]=(elep){mid+1,tre[o].r};
}
updat(tre[o].rv,num);
}
puhigh(o);
}
int merge(int o1,int o2){
if(!o2)return o1;
if(!o1)return o2;
if(tre[o1].l==tre[o1].r){tre[o1].val+=tre[o2].val;return o1;}
tre[o1].lv=merge(tre[o1].lv,tre[o2].lv);
tre[o1].rv=merge(tre[o1].rv,tre[o2].rv);
puhigh(o1);
return o1;
}
int query(int o,int num){
if(!o)return 0;
if(tre[o].l==tre[o].r)return tre[o].val;
int mid=(tre[o].l+tre[o].r)>>1;
if(num<=mid) return query(tre[o].lv,num);
if(mid+1<=num)return query(tre[o].rv,num);
}
void dfs2(int o){
updat(o,dep[o]);
mar(o){
if(dep[v]<dep[o])continue;
dep[v]=dep[o]+1;
dfs2(v);
merge(o,v);
}
int siz=vec[o].size()-1;
rep(i,0,siz)ans[ vec[o][i] ]=query(o,qq[ vec[o][i] ].ned)-1;
}
void dfs1(int o){
rep(i,1,17)fc[o][i]=fc[ fc[o][i-1] ][i-1];
mar(o){
if(dep[v])continue;
fc[v][0]=o;
dep[v]=dep[o]+1;
dfs1(v);
}
}
void fimd(int id){
galo z=qq[id];
per(i,17,0){
if((1<<i)>z.ned)continue;
z.o=fc[z.o][i];
z.ned=z.ned-(1<<i);
}
qq[id].o=z.o;
qq[id].ned=qq[id].ned+dep[z.o];
vec[z.o].push_back(id);
}
int main(){
scanf("%d",&n);
rep(i,1,n)tre[i]=(elep){1,100000};
cnt=n;
rep(i,1,n){
int x;scanf("%d",&x);
if(x)edge(x,i);
else rotc++,rot[rotc]=i;
}
rep(i,1,rotc){
dep[ rot[i] ]=1,dfs1( rot[i] );
}
scanf("%d",&T);
rep(i,1,T){
scanf("%d%d",&qq[i].o,&qq[i].ned);
fimd(i);
}
rep(i,1,rotc)dfs2( rot[i] );
rep(i,1,T)printf("%d ",ans[i]);
return 0;
}