题解：P16905 [CCO 2026] Tree Traversals

_Communist · 2026-11-12 20:49:06 · 题解

来个普及组小朋友都会写的在线线性实现，懒得卡常，但是好写就对了。

首先有深度不降的限制，不妨记深度为 i 的点集为 S_i。那么由虚树的经典结论，S_i 之间任意排列，都至少会经过一次 \text{LCA}(S_i)。于是同层点内部要求 2(i-\text{dep}(\text{LCA}(S_i)))\le k，可以得到一个 k 的下界 L。当 k<L 时，答案全部为 0。

这里讲讲如何简单求出 \text{LCA}(S_i)。注意到 \text{LCA}(S_i) 一定是 \text{LCA}(S_{i+1}) 的祖先，因为一个在 S_{i+1} 中的点它的父亲一定在 S_i 中（废话）。令最大深度为 m，先 O(n) 求出 \text{LCA}(S_m)。回归最近公共祖先的定义，在已知 \text{LCA}(S_{i+1}) 后，我们不断往上跳父亲直到子树内包含了所有 S_i 的点，就找到了 \text{LCA}(S_i)。检查子树内是否包含所有 S_i 的点可以用 dfs 序 O(1) 判断。

:::info[这一部分的代码]

void getlca() {
    auto check = [&](int u, int d) { return vec[d][0] >= dfn[u] && vec[d].back() <= dfr[u]; };
    //vec[d] 存储了深度为 d 的节点的 dfn
    int u = 0;
    for (int i = 1; i <= n; ++i) {
        if (check(i, m) && (!u || dep[i] > dep[u])) u = i;
    }
    lca[m] = u;
    for (int i = m - 1; ~i; --i) {
        while (fa[u] && !check(u, i)) u = fa[u]; 
        lca[i] = u;
    }
}

:::

接下来考虑相邻层之间的移动，假设 S_i 排列后最后一个点为 x，要移动到 S_{i+1} 中。发现最大的可能距离为 2(i-\text{dep}(\text{LCA}(S_i)))+1，也就是说只要 k 大于等于下界 L+1，就随便乱排就合法，阶乘全部乘起来即可。

此时只剩下 k=L 的答案。考虑一个 x 是怎么取到上面说的“最大的可能距离”的，发现一定是 x 与 S_{i+1} 分居 \text{LCA}(S_i) 的不同子树。

于是在求 \text{LCA}(S_i) 的过程中记录一下 \text{LCA}(S_{i+1}) 在它的哪个子树，所有在这里面的 x\in \text{LCA}(S_i) 都可以作为 S_i 这一层的结尾。注意当 \text{LCA}(S_i)=\text{LCA}(S_{i+1}) 时可以随便乱排 S_i。

:::info[求答案部分的代码]

void solve() {
    int lim = 0;
    for (int i = 0; i <= m; ++i) {
        lim = max(lim, (i - dep[lca[i]]) << 1);
    }
    fill(ans, ans + 1 + n, 0);
    if (lim > n) return;
    int res = 1;
    for (int i = 0; i <= m; ++i) tim(res, fac[vec[i].size()]);
    fill(ans + 1 + lim, ans + 1 + n, res);
    res = 1;
    for (int i = 0; i <= m; ++i) {
        int x = 0;
        if (lst[i] && lim == ((i - dep[lca[i]]) << 1)) {
            for (int v : vec[i]) if (v >= dfn[lst[i]] && v <= dfr[lst[i]]) ++x;
        } else x = vec[i].size();
        tim(res, x), tim(res, fac[(int)vec[i].size() - 1]);
    }
    ans[lim] = res;
}

:::