题解：P16905 [CCO 2026] Tree Traversals

· · 题解

分析

首先 p 应该是一个类似于 BFS 序的东西，也就是按照深度一层一层加的。

对于 u，记 mdep_u 为 u 子树中最大深度点。那么如果 f(K)\ge 1，首先需要满足对任意 u 的两个儿子 v_1,v_2，有 2\min(mdep_{v_1},mdep_{v_2})-2dep_u \le K。因为这个深度的点肯定会跨越。

这样 d(p_{i-1},p_i)\le K 的限制就只针对 dep_{p_i} = dep_{p_{i-1}}+1 的 (p_{i-1},p_i) 了。

定义状态函数 f_{u} 表示只考虑 u 子树时合法的相对顺序。现在将 u 的儿子 v 合并起来。合并后的顺序合法，当且仅当对于一个深度 d 的最后一个点，若 2d - 2dep_u+1 > K，则此时这个点和下一个点不能不属于同一个子树。

解得 d\ge \lceil\frac{K+2dep_u}{2}\rceil 。不难发现，这需要满足 u 只有最多一个儿子 v 满足 mdep_v \ge \lceil\frac{K+2dep_u}{2}\rceil + 1。因为如果有两个儿子满足，2\min(mdep_{v_1},mdep_{v_2})-2dep_u 就大于 K 了。

记 d_0 = \lceil\frac{K+2dep_u}{2}\rceil。在 mdep_u \ge d_0 时就只需要满足合并后最后一个深度为 d_0 的点属于 mdep_v > d_0 的那个儿子子树（mdep_u= d_0 或者不存在 mdep_v = d_0 的儿子则无限制）。

显然，这个儿子一定是 u 的长儿子。

记 F = \prod\limits_{dep = 1}^{mdep_1}cnt(dep)!，表示初始可能排列数量。对于 u，记 u 儿子中 mdep_v 的最大值和次大值分别是 x,y。在 y + 1 = x 时：

这样长剖一下就能直接维护 \Delta(K) 了。

时间复杂度 O(n)。

我写的 O(n\log V)，用快速幂求了下逆元。

代码

const int N = 1e6 + 10, mod = 1e9 + 7;
int n, q;
vector<int> e[N];
int dep[N], mdep[N], id[N], L[N], R[N];
vector<int> cnt[N];
int fac[N], inv[N];
int Cnt[N], dt[N];
int Kmin;

il int C(int n, int m){
    if(n < m || m < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
il void init(){
    fac[0] = 1;
    UU(i, 1, N) fac[i] = fac[i - 1] * i % mod;
    UU(i, 0, N) inv[i] = qmi(fac[i], mod - 2, mod);
    return ;
}
il void dfs0(int u, int fa){
    dep[u] = dep[fa] + 1;
    ++ Cnt[dep[u]];
    mdep[u] = dep[u], id[u] = u;
    for(auto v: e[u]) if(v != fa){
        dfs0(v, u);
        if(mdep[v] > mdep[u]) mdep[u] = mdep[v], id[u] = id[v];
    }
    R[id[u]] = max(R[id[u]], dep[u]);
    L[id[u]] = dep[u];
    return ;
}
il void dfs1(int u, int fa){
    int mdep_ = -1;
    for(auto v: e[u]) if(v != fa){
        dfs1(v, u);
        if(id[v] != id[u]) mdep_ = max(mdep_, mdep[v]);
    }
    if(~mdep_) Kmin = max(Kmin, 2 * mdep_ - 2 * dep[u]);
    int cnt_ = (mdep_ != -1 ? cnt[id[u]][mdep_ - L[id[u]] + 1] : 0);
    for(auto v: e[u]) if(v != fa && id[v] != id[u]){
        U(x, 1, R[id[v]] - L[id[v]] + 1){
            int Dep = L[id[v]] + x - 1 - L[id[u]] + 1;
            cnt[id[u]][Dep] += cnt[id[v]][x];
        }
    }
    ++ cnt[id[u]][dep[u] - L[id[u]] + 1];
    if(mdep_ + 1 <= mdep[u] && (~mdep_)){
        // assert(mdep_ + 1 <= mdep[u]);
        int k_ = 2 * mdep_ - 2 * dep[u];
        int Delta = C(cnt[id[u]][mdep_ - L[id[u]] + 1] - 1, cnt_ - 1) * qmi(C(cnt[id[u]][mdep_ - L[id[u]] + 1], cnt_), mod - 2, mod) % mod;
        U(k, k_ - 1, k_ + 1) if(k >= 0){
            if((k + 2 * dep[u] - 1) / 2 + 1 == mdep_){
                dt[k] = dt[k] * Delta % mod;
            }
        }
    }
    return ;
}

il void solve(){ 
    n = rd, q = rd;
    {
        Kmin = 0;
        U(i, 0, n + 1){
            L[i] = R[i] = 0;
            vector<int> ().swap(e[i]);
            vector<int> ().swap(cnt[i]);
            Cnt[i] = 0;
            dt[i] = 1;
        }
    }
    UU(i, 1, n){
        int u = rd, v = rd;
        e[u].emplace_back(v),
        e[v].emplace_back(u);
    }
    dfs0(1, 0);
    U(i, 1, n) if(id[i] == i){
        cnt[i].resize(R[i] - L[i] + 2);
        U(x, 1, R[i] - L[i] + 1) cnt[i][x] = 0;
    }
    int F = 1;
    U(i, 1, mdep[1]) F = F * fac[Cnt[i]] % mod;
    dfs1(1, 0);
    while(q --){
        int K = rd;
        if(K < Kmin) cout << "0 ";
        else cout << F * dt[K] % mod << " ";
    }
    puts("");
    return ;
}