CF208E Blood Cousins

· · 个人记录

题目链接。

dsu on tree 是什么，本蒟蒻不知道啊。于是本蒟蒻用模拟切了这个题（bushi）。

无任何高级数据结构，甚至连 dfs 序啥的都没有（？）。

首先第一步是显然的，对 v 求 k 级祖先 u，然后询问变成了询问 u 有多少个 k-son（答案要减 1）。

一个节点的 K-Son 即为在该节点子树内的，深度是该节点深度加 K 的节点。

—— CF246E Blood Cousins Return

这个加强版甚至已经帮你把第一步做好了。

对于第二步，把所有询问离线下来。

我们先考虑简单一点的情况：如果所有询问都是在根上那么怎么做。容易发现此时任何点都在该点子树内，所以我们只需要统计这棵树内有多少个深度为 该节点深度 +k 的点即可。dfs 一遍这棵树，记录一个数组 num[] 表示每种深度有多少个点即可。

考虑拓展。如果不是在根询问仍然可以做，但是可能会有不在子树内的点计入答案。很简单啊，dfs 进入这个节点和快要退出的时候显然只有这个子树内的点改变了 num 数组。那么退出时的 num 减去进入的 num 显然就是只考虑子树的 num 了。

如果扔掉树上 k 级祖先，复杂度是 O(n) 的。但是我不会长链剖分，如果用长剖做第一步是不是总复杂度就 O(n) 了/jk

AC code：

// 省去一堆缺省源
const int DUST = 327, N = 114514, M = -1;
int head[N], to[N], ne[N], idx1 = 0;
void add(int u, int v) {
    to[idx1] = v, ne[idx1] = head[u], head[u] = idx1++;
}
int fa[20][N], dph[N], num[N];
vector<pii> qs[N];// x: k, y: id
int output[N];
int getfa(int u, int k) {
    for(int j = 0; j < 20; j++) if(k >> j & 1) u = fa[j][u];
    return u;
}
void dfs(int u) {
    dph[u] = dph[fa[0][u]] + 1, num[dph[u]]++;
    for(auto q : qs[u])
        output[q.y] -= num[dph[u] + q.x];
    for(int e = head[u], v; ~e; e = ne[e]) if((v = to[e]) != fa[0][u])
        dfs(v);
    for(auto q : qs[u])
        output[q.y] += num[dph[u] + q.x] - 1;//减去询问的点自己（）
}
bool major(int Case = 1) {
    memset(head, -1, sizeof head);
    int n = read();
    for(int i = 1; i <= n; i++) add(fa[0][i] = read(), i);

    for(int j = 1; j < 20; j++)
        for(int u = 1; u <= n; u++)
            fa[j][u] = fa[j - 1][fa[j - 1][u]];
    int q = read();
    for(int i = 1; i <= q; i++) {
        int v = read(), k = read(), u = getfa(v, k);
        qs[u].eb(k, i);
    }
    for(int i = 1; i <= n; i++) if(!fa[0][i]) dfs(i);
    for(int i = 1; i <= q; i++) printf("%d%c", output[i], " \n"[i == q]);
    return Case ^= Case ^ Case;
}