题意:有一颗树,根结点为\(1\).\(q\)个询问,每次问你共有多少经过\(u\)点且到根节点距离为\(d\)的点.

题解:这题技巧性好强,我们从根节点遍历整颗树,用时间轴记录搜到和离开的时间\(in_i\)和\(out_i\),同时存入同一深度的所有\(in_i\),方便后面计算.对于某个父亲结点\(u\),它的一个子树结点为\(v\),必然满足:\(in_u\le in_v <out_u\).那么对于每次询问的\(U_i\),我要去找深度为\(d\)的它或它的子树结点,也就是找出所有深度为\(d\)且满足\(in_u\le in_i<out_u\)的点,这里可以用二分查找.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int n;
int p;
vector<int> edge[N];
int q;
int u,d;
vector<int> v[N];
int timestamp;
int in[N],out[N];

void dfs(int u,int dep){
	in[u]=timestamp++;
	v[dep].pb(in[u]);
	for(auto w:edge[u]){
		dfs(w,dep+1);	
	}	
	out[u]=timestamp++;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;++i){
		cin>>p;
		edge[p].pb(i);
	}

	dfs(1,0);

	cin>>q;
	for(int i=1;i<=q;++i){
		cin>>u>>d;
		cout<<lower_bound(v[d].begin(),v[d].end(),out[u])-lower_bound(v[d].begin(),v[d].end(),in[u])<<'\n';
	}


    return 0;
}