CF208E Blood Cousins

Blood Cousins - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

用倍增可以快速求出 $v_i$ 的 $p_i$ 级祖先 $u_i$，然后对 $u_i$ 打上标记，表示它与询问 $i$ 有关。标记可用 vector 维护。

接着第一次 dfs 求出每个结点的深度和重儿子。第二遍 dfs 计算以不同点为根的子树中分别有多少个对应深度的结点，以深度为下标开桶计算。此处使用树上启发式合并，轻儿子子树暴力遍历，重儿子子树的信息直接获取。

时间复杂度 $O(n\log n)$。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, logN = 21;

int n, m, fa[N][logN + 5], son[N], dep[N], siz[N], cnt[N], ans[N];
vector<int> g[N], que[N];
struct Query {
    int x, k, u;
} q[N];

void dfs1(int u)
{
    siz[u] = 1;
    for (auto v : g[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]])
            son[u] = v;
    }
}

void clear(int u)
{
    cnt[dep[u]]--;
    for (auto v : g[u])
        clear(v);
}

void calc(int u, int S)
{
    cnt[dep[u]]++;
    for (auto v : g[u]) {
        if (v == S) continue;
        calc(v, S);
    }
}

void dfs2(int u)
{
    if (u == 0) {
        for (auto v : g[u]) {
            dfs2(v);
            clear(v);
        }
        return;
    }
    for (auto v : g[u]) {
        if (v == son[u]) continue;
        dfs2(v);
        clear(v);
    }
    if (son[u])
        dfs2(son[u]);
    calc(u, son[u]);
    for (auto k : que[u])
        ans[k] = cnt[q[k].k + dep[u]] - 1;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &fa[i][0]);
        g[fa[i][0]].push_back(i);
    }
    for (int i = 1; i <= logN; i++)
        for (int j = 1; j <= n; j++)
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
    dfs1(0);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &q[i].x, &q[i].k);
        int p = q[i].k, u = q[i].x;
        for (int j = logN; ~j; j--) {
            if (p >= (1 << j)) {
                p -= (1 << j);
                u = fa[u][j];
            }
        }
        q[i].u = u;
        que[u].push_back(i);
    }
    dfs2(0);
    for (int i = 1; i <= m; i++)
        printf("%d ", ans[i]);
    return 0;
}