题解 CF208E 【Blood Cousins】

原题链接：CF208E Blood Cousins

题意简述

• 给定 n 个结点的森林，边权为 1；一共 m 次询问，每次询问一个结点 p 与多少个结点拥有共同的 K 级祖先。

• 1 \le n, m \le 10^5

思路与解答

• 首先考虑求出询问中每个结点的 K 级祖先，就可以将问题转化为对于一个结点 u，在它的子树中有多少个与它距离为 K 的结点，其中 u 是对应的 p 的 K 级祖先。

• 每一次询问的答案就是上一步求出的答案减一（因为要去除 p）

• 然后可以把这道题分成两部分：第一部分是求出 K 级祖先，第二部分是对于上一步中的每一个 K 级祖先求出答案。

• 首先来看第一部分

• 这显然是一个经典的问题，运用长链剖分可以做到 \Theta(m) 的时间复杂度；但是你发现这题并没有卡掉带 \log 的做法，所以预处理一下，然后倍增跳祖先即可，时间复杂度 \Theta(m \log n)。

• 这一部分就结束啦~

• 然后是第二部分

• 发现这是一个子树中的统计问题，你需要统计子树中深度与 p 相同的结点的数量，所以考虑 dsu on tree

• 如果你不知道什么是 dsu on tree，可以学习一下这个视频（不是广告QAQ），我就是从同学的讲课和这里学会的。

• 考虑你需要维护什么信息，不妨按照套路开一个桶，记录当前结点的子树中深度为 x 的点的数量。

• 那么对于每一个询问，在遍历到 K 级祖先时，按照惯例保留重儿子的贡献、暴力统计轻儿子的贡献，然后看看和当前询问的 p 的深度相同的点有多少个（这东西已经开桶维护了），只要把这个数量减一就是答案了（好像刚才已经说过了）。

• 这部分的复杂度就是 \Theta(n \log n)，所以总复杂度就是 \Theta(m \log n + n \log n)

Code

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 100010;

int n, m;

struct edge{
    int ne, to;
}e[MAXN];
int fir[MAXN], num = 0;
inline void join(int a, int b)
{
    e[++num].ne = fir[a];
    e[num].to = b;
    fir[a] = num;
}
int rt[MAXN], tot = 0;

int siz[MAXN], son[MAXN], f[MAXN][24], dep[MAXN], lg[MAXN];

void dfs1(int u)
{
    siz[u] = 1; dep[u] = dep[f[u][0]] + 1;
    for(int i=1;i<=lg[dep[u]];i++)
        f[u][i] = f[f[u][i-1]][i-1];
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        dfs1(v);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
inline int kthparent(int u, int k)
{
    for(int i=lg[dep[u]];i>=0;i--)
        if(dep[u] - dep[f[u][i]] <= k) k -= dep[u] - dep[f[u][i]], u = f[u][i];
    return u;
}

struct qrys{
    int x, k, pa, ans;
}a[MAXN];
vector<int> vp[MAXN];

int cnt[MAXN], nowson = 0;
void calc(int u, int val)
{
    cnt[dep[u]] += val;
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == nowson) continue;
        calc(v, val);
    }
}

void dfs(int u, bool is)
{
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == son[u]) continue;
        dfs(v, 0);
    }
    if(son[u]) 
    {
        dfs(son[u], 1);
        nowson = son[u];
    }
    calc(u, 1);
    nowson = 0;
    for(int i=0;i<vp[u].size();i++)
        a[vp[u][i]].ans = cnt[dep[a[vp[u][i]].x]]-1;
    if(!is) calc(u, -1);
}

int main()
{
    scanf("%d",&n);
    lg[0] = -1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][0]);
        if(f[i][0]) join(f[i][0], i);
        else rt[++tot] = i;
        lg[i] = lg[i>>1] + 1;
    }
    for(int i=1;i<=tot;i++)
        dfs1(rt[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].k);
        a[i].pa = kthparent(a[i].x, a[i].k);
        vp[a[i].pa].push_back(i);
    }
    for(int i=1;i<=tot;i++)
        dfs(rt[i], 0);
    for(int i=1;i<=m;i++)
        printf("%d%c",a[i].ans," \n"[i==m]);
    return 0;
}