题意

给出一棵家谱树，定义从 u 点向上走 k 步到达的节点为 u 的 k-ancestor。多次查询，给出 u k，问有多少个与 u 具有相同 k-ancestor 的节点。

分析

设 rt 为 u 的 k-ancestor。问题可以转换成在以 rt 为根的子树下，有多少个节点的深度与 u 相同。

预处理出离 u 距离为 k 的祖先 rt 。

我们可以把所有的查询用向量存起来（祖先节点，要查询的节点的深度，对应查询的id），在遍历到某个祖先节点时，统计那个子树下，我们所要查询的某个节点深度的数量，直接去更新答案。也就是说子树的状态信息（数量信息）可以复用，也就是说可以套用 树上启发式合并。

code

#include
    
     using namespace std;typedef long long ll;const int MAXN = 1e5 + 10;int n;int fa[MAXN][20], son[MAXN], dep[MAXN], siz[MAXN];int col[MAXN];int cnt, head[MAXN];struct Edge {    int to, next;} e[MAXN << 1];struct Ex {    int x, c;};vector
     
       ex[MAXN];void addedge(int u, int v) {    e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++;    e[cnt].to = u; e[cnt].next = head[v]; head[v] = cnt++;}void dfs(int u) {    siz[u] = 1;    son[u] = 0;    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];    for(int i = head[u]; ~i; i = e[i].next) {        if(e[i].to != fa[u][0]) {            fa[e[i].to][0] = u;            dep[e[i].to] = dep[u] + 1;            dfs(e[i].to);            if(siz[e[i].to] > siz[son[u]]) son[u] = e[i].to;            siz[u] += siz[e[i].to];        }    }}int getAn(int u, int d) {    for(int i = 0; i < 20; i++) {        if(d >> i & 1) {            u = fa[u][i];        }    }    return u;}int vis[MAXN], ans[MAXN], C[MAXN];void change(int u, int c) {    C[dep[u]] += c;    for(int i = head[u]; ~i; i = e[i].next) {        if(e[i].to != fa[u][0] && !vis[e[i].to]) change(e[i].to, c);    }}void dfs1(int u, int flg) {    for(int i = head[u]; ~i; i = e[i].next) {        if(e[i].to != fa[u][0] && e[i].to != son[u]) dfs1(e[i].to, 1);    }    if(son[u]) {        dfs1(son[u], 0);        vis[son[u]] = 1;    }    change(u, 1);    int sz = ex[u].size();    for(int i = 0; i < sz; i++) {        ans[ex[u][i].x] = C[ex[u][i].c];    }    if(son[u]) vis[son[u]] = 0;    if(flg) change(u, -1);}int main() {    scanf("%d", &n);    memset(head, -1, sizeof head);    cnt = 0;    for(int i = 1; i <= n; i++) {        int x;        scanf("%d", &x);        addedge(i, x);    }    dfs(0);    int m;    scanf("%d", &m);    for(int i = 0; i < m; i++) {        int x, y;        scanf("%d%d", &x, &y);        if(dep[x] - y <= 0) {            ans[i] = 1;            continue;        }        int anc = getAn(x, y);        ex[anc].push_back(Ex{i, dep[x]});    }    dfs1(0, 0);    for(int i = 0; i < m; i++) {        printf("%d%c", ans[i] - 1, " \n"[i == m - 1]);    }    return 0;}