【題解】Codeforces 208E. Blood Cousins

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int maxn = 100005;
int n, m, p[maxn][20], in[maxn], out[maxn], idx, d[maxn];
vector <int> v[maxn], vd[maxn];
 
void f(int x, int dep){
    in[x] = idx;
    idx++;
    d[x] = dep;
    vd[dep].push_back(in[x]);
    for (int i:v[x]){
        f(i, dep+1);
    }
    out[x] = idx;
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> p[i][0];
        v[p[i][0]].push_back(i);
    }
    for (int j = 1; j < 20; j++){
        for (int i = 1; i <= n; i++){
            p[i][j] = p[p[i][j-1]][j-1];
        }
    }
    f(0, 0);
    cin >> m;
    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        for (int i = 0; i < 20; i++){
            if (y & (1<<i)) x = p[x][i];
        }
        if (x == 0){
            cout << 0 << " ";
            continue;
        }
        int tmp = d[x]+y;
        cout << upper_bound(vd[tmp].begin(), vd[tmp].end(), out[x])-lower_bound(vd[tmp].begin(), vd[tmp].end(), in[x])-1 << " ";
    }
}