题解：P14780 [COCI 2025/2026 #3] 国家 / Drzava

· · 题解

这是一篇拉格朗日插值的题解。

分析

我们先把选首都和次级共 k 个改成选 k-1 个合法的次级，然后确定首都的位置。

设答案为 c_0,c_1,...,c_{n-1}，令多项式 F(x) = \sum_{i=0}^{n-1}c_ix^{i}，那么我们只需要求出 F(x) 的系数就行了。

直接换根 DP 这个系数不太好做，我们考虑带几个点进去，求出 n 个点值，再拉格朗日插值得到系数。

即带入 x=0,1,...,n-1 这 n 个，我们发现 F(x) 的式子在带入 x 之后非常简单，相当于每个大小为 k 的合法次级城市集合贡献 x^k。

换根 DP：f_i 表示 i 子树内（不包括 i 自己）的贡献和，g_i 表示除去 i 子树的贡献和，f_i=x+\Pi_{j \in son}f_j，g 同理。

那么计算一个 x 的点值的复杂度就只有 O(n)，带 n 个总时间复杂度 O(n^2)，拉格朗日时间复杂度也是 O(n^2)，最终复杂度 O(n^2)。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll read() {
    ll n = 0 ,f = 1; char c = getchar();
    while (c < '0' || c > '9') f = (c == '-' ? -f : f) ,c = getchar();
    while (c >= '0' && c <= '9') n = n * 10 + c - '0' ,c = getchar();
    return n * f;
}

const ll mod = 1e9 + 7;
const int N = 3010;

int n; ll s;
vector<int> G[N];
ll f[N] ,g[N] ,y[N];
ll fac[N] ,coe[N] ,tmp[N] ,ans[N] ,poly[N];

ll qpow(ll a ,ll b = mod - 2) {
    ll res = 1;
    for (;b;b >>= 1 ,a = a * a % mod) if (b & 1) res = res * a % mod;
    return res;
}

void dfs1(int u ,int par ,ll x) {
    f[u] = 1;
    for (auto v : G[u]) if (v != par)
        dfs1(v ,u ,x) ,f[u] = f[u] * (f[v] + x) % mod;
}
void dfs2(int u ,int par ,ll x) {
    s = (s + g[u] * f[u]) % mod;
    ll mul = 1;
    for (auto v : G[u]) if (v != par) mul = mul * (f[v] + x) % mod;
    for (auto v : G[u]) if (v != par)
        g[v] = (g[u] * mul % mod * qpow((f[v] + x) % mod) % mod + x) % mod ,dfs2(v ,u ,x);
}

int main() {
    n = read();
    for (int i = 1 ,u ,v;i < n;i++)
        u = read() ,v = read() ,
        G[u].push_back(v) ,G[v].push_back(u);
    if (n == 1) return puts("1") ,0;

    //求 x = 0,1,...,n-1 的点值 
    for (int i = 0;i < n;i++) {
        dfs1(1 ,0 ,i);
        s = 0 ,g[1] = 1; dfs2(1 ,0 ,i);
        y[i] = s;
    }

    //拉格朗日求系数板子
    fac[0] = 1;
    for (int i = 1;i < n;i++) fac[i] = fac[i - 1] * i % mod;

    coe[0] = 1;
    for (int i = 0;i < n;i++) {
        for (int j = i;j >= 0;j--)
            tmp[j + 1] = (tmp[j + 1] + coe[j]) % mod ,
            tmp[j] = (tmp[j] - coe[j] * i % mod + mod) % mod;
        for (int j = 0;j <= i + 1;j++) coe[j] = tmp[j] ,tmp[j] = 0;
    }

    for (int i = 0;i < n;i++) {
        ll Coe = fac[i] * fac[n - 1 - i] % mod;
        if ((n - 1 - i) & 1) Coe = (mod - Coe) % mod;
        Coe = qpow(Coe) * y[i] % mod;

        for (int j = 0;j <= n;j++) tmp[j] = coe[j];
        for (int j = n - 1;j >= 0;j--)
            poly[j] = tmp[j + 1] ,
            tmp[j] = (tmp[j] + i * poly[j]) % mod;

        for (int j = 0;j < n;j++) ans[j] = (ans[j] + Coe * poly[j]) % mod;
    }

    for (int i = 0;i < n;i++) printf("%lld ",ans[i]);
    puts("");

    return 0;
}