题解 [省选联考 2020 B 卷] 消息传递

省流：

~~长剖做法，全网首发，最优拿下，把某点分治吊杀。~~

实际上卡满的话没有点分治快。

长链剖分属于树链剖分的一种。不过重儿子是子树深度最大的那个儿子（称为长儿子）。

长剖性质有：

长链的长度之和为 $O(n)$ 。
对于树上的任何一个点跳长链到根，需要经过不超过 $O(\sqrt{n})$ 条长链。长链的长度依次为 $1,2,3,\cdots,\sqrt{n}$ 时卡满。

由于第二条性质，使得长剖的发挥空间比重剖小。不过由于长剖独特的定义，使得其可以在与距离相关的部分问题中，给出线性且低常数神奇做法。比如长剖优化DP。

我们用 $son[u]$ 表示非叶子节点 $u$ 的长儿子。

定义 $f[u][i]$ 为以 $u$ 为根的子树中，与 $u$ 距离为 $i$ 的点的个数。我们每个节点的状态直接继承其长儿子的节点状态（ $f[u][i]\gets f[son[u]][i-1]$ ），同时将短儿子的 DP 状态暴力合并。

有意思的是，由于继承的过程可以视为 DP 数组整体后移一位，所以可以利用指针 $O(1)$ 的实现这个过程。而每个长链只会被暴力合并一次，所以时间总复杂度是 $O(n)$ 的。同时，每个叶子节点需要 $O(1)$ 的空间，每个非叶子节点由于继承了长儿子，只需要 $O(1)$ 的额外空间，所以空间总复杂度也是 $O(n)$ 的。

为什么不能用重剖实现呢？重剖不同与长剖，无法保证重儿子的子树深度不小于轻儿子的子树深度。这会使得合并时没有对应的空间存储 DP 状态。

注意，由于长儿子的 DP 数组会被继承走，所以询问要挂在点上，不能在线。虽然短儿子的 DP 数组不会受到影响。

做到这里，我们已经把子树内的贡献解决了。然后发现子树外的不是很好做。如果定义 $g[u][i]$ 为以 $u$ 为根的子树外，与 $u$ 距离为 $i$ 的点的个数，时空复杂度完全无法承受。我为此困惑了很久（~~试图长剖换根 DP~~）。回顾 $f$ 的过程，发现状态数由链长限制，这启发我们把 $g[u][i]$ 限制到长链以内。即重新定义 $g[u][i]$ 为以 $u$ 所在长链的链顶为根的子树内，以 $u$ 为根的子树外，与 $u$ 距离为 $i$ 的点的个数。此时状态数被控制在了二倍链长以内（从长链的底端的叶子到另一个叶子，而另一个叶子的深度不大于长链的底端的叶子）。

明确了 $g$ 之后，转移不难。如果自己是长儿子，就继承父亲。然后再暴力合并上短儿子的 $f$ 。这里是 $f$ 哦，看清！

注意， $f$ 是自下而上的， $g$ 是自上而下的，继承方向相反，注意实现（看注释）。

长链内的信息，我们可以用 $f[u]$ 和 $g[u]$ 保证。但可能有长链外的信息遗失。跳长链即可。这里不好讲解，看注释。

但时间复杂度也无奈的来到了 $O(n+q\sqrt{n})$ 。~~但是常数就是小啊，你来打我呀～~~

代码较短，不过细节较多。

code

const int N = 1e5 + 7;

int n, m;

struct E {
    int to, ne;
} e[N << 1];
int h[N];
int idx;

inline void add(int x, int y) {
    e[ ++ idx] = (E){y, h[x]};
    h[x] = idx;
}

vector<pair<int, int>> Q[N];
int ans[N];

int hei[N];  // 子树深度
int son[N];  // 长儿子
int far[N];  // 父亲
int top[N];  // 链顶
int dfn[N];  // 长剖后的 dfs 序
int dnt;
int fff[N];  // f 的空间池

int zero = 0;  // 无奈之举

/*
 ! ! ! !   马蜂警告   ! ! ! !

对于一个数组 shuzu[]
一般下标为 i 的元素由 shuzu[i] 表达
如果你看到 i[shuzu] 的写法，请不要惊惶，这与上面等价
注释里我尽可能避免下面这个写法

 - - - -   一些规定   - - - -

注释里，
top直接表示长链链顶节点
btm直接表示长链链底节点

有 dfn[btm] = dfn[top] + hei[top] - 1

*/

// 第一遍dfs 长剖
void dfs1(int u, int fa) {
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].to;
        if (v == fa) continue;
        dfs1(v, u);
        if (u[son][hei] < v[hei]) {
            u[son] = v;
        }
    }
    u[far] = fa;
    u[hei] = u[son][hei] + 1;
}

/*
由于本人不喜指针，故利用 dfs 序实现O(1)继承
我们把 f[u][0] 放在 fff[dfn[u]] 处
这样 f[u][1] 从 f[son[u]]][0] 继承时，
fff[dfn[son[u]]] <=> fff[dfn[u]]

一段长链的空间范围为 【 dfn[top] ， dfn[btm] 】
*/

inline int &f(int i, int j) {
    if (j >= hei[i] || j < 0) return zero;  //  询问里的 k 可能超过当前链长
    else return fff[i[dfn] + j];
}

// 第二遍 dfs 求 f
void dfs2(int u, int tp) {
    u[top] = tp;
    u[dfn] = ++ dnt;
    if (u[son]) {
        dfs2(u[son], tp);
    }
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].to;
        if (v == u[far] || v == u[son]) {
            continue;
        }
        dfs2(v, v);
    }
    /*
    注意，这里并没有合并短儿子
    f 仅包含长儿子内的信息
    */
    
    for (auto i : Q[u]) {
        int x = u;
        int y = i.second;
        while (x && y >= 0) {
            ans[i.first] += f(x, y);
            // 跳长链
            y -= x[top][hei] - x[hei] + 1;
            x = x[top][far];
        }
    }
    
    // 合并信息
    f(u, 0) = 1;
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].to;
        if (v == u[far] || v == u[son]) {
            continue;
        }
        for (int j = 0; j < v[hei]; ++ j) {
            f(u, j + 1) += f(v, j);
        }
    }
}

int ggg[N * 2];

/*

构造 g 的空间有点麻烦

先确认左极限 g[top][hei[top] - 1]
  确认右极限 g[btm][0]
  需要 2 * hei[top] - 1 的空间
  确认大致空间范围 【 2*(dfn[top]) ， 2*(dfn[btm]) 】

链长为 4，dfn[top] = 6 时，
dfn[btm] = 9;

在空间池里状态：
下标  10  11  12  13  14  15  16  17  18  19  20 
     ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— 
    |   |   | + | + | + | + | + | + | + |   |   |
     ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— 
              ^           ^       ^   ^
              |     g[top][0]     |  g[btm][0]
    g[top][hei[top] - 1]     g[btm][1]

于是可以构造 g[u][0] 为 ggg[dfn[btm]*2 - (hei[u] - 1)]
                    => ggg[dfn[btm] + dfn[u]]
            g[u][i] 为 ggg[dfn[btm] + dfn[u] - i]
                    => ggg[dfn[top] + hei[top] - 1 + dfn[u] - i]
*/

inline int &g(int i, int j) {
    if (i[top][hei] + i[top][hei] - i[hei] <= j) return zero;
    return ggg[i[dfn] + i[top][dfn] + i[top][hei] - j - 1];
}

// 第三遍 dfs 求 g
void dfs3(int u) {
    /*
    此时 g 为 u 子树以外的信息
    */
    g(u, 0) = 1;
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].to;
        if (v == u[far] || v == u[son]) continue;
        for (int j = 0; j < v[hei]; ++ j) {
            g(u, j + 1) += f(v, j);
            /*
            因为短儿子的 DP 数组不会被继承
            所以 f(v, j) 是可用的
            */
        }
    }
    /*
    此时 g 为长儿子以外的信息
    */
    for (auto i : Q[u]) {
        // 本长链内，长儿子外的信息
        ans[i.first] += g(u, i.second);
        
        int x = u[top];
        int y = i.second - x[hei] + u[hei];
        while (x > 1 && y > 0) {
            /*
            注意这里脑抽的跳长链方式
            因为上一层里统计了这一层的信息（相当于走出长链又立刻走回来了
            所以我们要减去一个 f
            由于我们要同时访问两条链的信息，所以只能停在长链顶
            */
            ans[i.first] += g(x[far], y - 1) - f(x, y - 2);
            x = x[far];
            y -= x[top][hei] - x[hei] + 1;
            x = x[top];
        }
    }
    /*
    此时 g 为长儿子以外的信息，它还要处理短儿子内的询问
    */
    for (int i = h[u]; i; i = e[i].ne) {
        int v = e[i].to;
        if (v == u[far] || v == u[son]) continue;
        dfs3(v);
    }
    /*
    g[u] 使命结束，传给 g[son[u]]
    */
    if (u[son]) {
        dfs3(u[son]);
    }
}

inline void INIT() { }

inline void WORK() {
    rd(n, m);
    for (int i = 2; i <= n; ++ i) {
        int x, y;
        rd(x, y);
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= m; ++ i) {
        int x, k;
        rd(x, k);
        Q[x].push_back({i, k});
        ans[i] = 0;
    }
    dfs1(1, 0);
    dfs2(1, 1);
    dfs3(1);
    
    for (int i = 1; i <= m; ++ i) {
        wr(ans[i], '\n');
        ans[i] = 0;
    }
    
    idx = 0;
    dnt = 0;
    for (int i = 1; i <= n; ++ i) {
        h[i] = 0;
        hei[i] = 0;
        son[i] = 0;
        fff[i] = 0;
        ggg[i * 2] = 0;
        ggg[i * 2 + 1] = 0;
        Q[i].clear();
    }
}

本文由 Sin Watt 编写，采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。