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

· · 题解

怎么大家都会不依赖深度的做法 /ll 来一个依赖深度的退背包做法。

看完这个题，我会 O(n^3)！枚举根节点，然后记 f_{i,j} 为 i 节点的子树内选了 j 个关键节点的方案数，每次只需要让 f_{u,1} \leftarrow f_{u,1} + 1 就可以了。

考虑换根。用 F_{i,j} 继承上面的定义，让 f_{i,j} 为不考虑 i 节点本身被选中的情况数（其实就是 F_{i,1} = f_{i,1} + 1），设 g_{i,j} 为 i 节点子树外选 j 个节点的方案数，从上往下转移就是你要合并前后缀的 f 与 g_{fa}。

发现这个东西和 recollector 很像，但是还要包含 g_{fa}。我们考虑类似的处理手法，具体就是退背包解决。

设现在从 u 转移到 v，每次先让 f_{u} 和 g_{u} 合并，记为 h_{u}，然后每次要从 h_{u} 中去掉 F_{v} 的贡献得到 g_{v}。

分析一下复杂度，合并 f_u 和 g_u 的复杂度是 O(\sum siz(n-siz))，h_u 的大小是 n，从 h_u 中去掉 F_v 的贡献复杂度也是 O(\sum siz(n-siz))。

发现这个复杂度相当于枚举每一条边，左右两边子树大小乘起来。对于一个点对 (u,v)，它会产生的贡献为两点路径的边数，最大是题目中的常数 36，因此这个算法的复杂度是 O(n^2 l)，其中 l 为两点间距离，也可以理解为深度。

::::info[Code]

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

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

ll qpow(ll a,int b)
{
    ll ret=1;
    while(b)
    {
        if(b&1) ret = ret*a % mod;
        a = a*a % mod;
        b >>= 1;
    }
    return ret;
}

int n;
vector<int> e[N];
int siz[N];
ll f[N][N],F[N][N],g[N][N];
ll f1[N],f2[N],ans[N];

void dfs(int u,int fa)
{
    siz[u] = 0;
    f[u][0] = 1;
    for(int v:e[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        for(int i=0;i<=siz[u];i++)
        {
            for(int j=0;j<=siz[v];j++)
            {
                f1[i+j] = (f1[i+j] + f[u][i] * F[v][j] % mod) % mod;
            }
        }
        siz[u] += siz[v];
        for(int i=0;i<=siz[u];i++)
        {
            f[u][i] = f1[i];
            f1[i] = 0;
        }
    }
    siz[u]++;
    // cerr << " ---- " << u << " ----\n";
    for(int i=0;i<=siz[u];i++)
    {
        F[u][i] = f[u][i];
        // cerr << f[u][i] << ' ';
    }
    // cerr << '\n';
    F[u][1] = (F[u][1] + 1) % mod;
    // for(int i=0;i<=siz[u];i++)
    // {
    //     cerr << F[u][i] << ' ';
    // }
    // cerr << '\n';
}

void dfs1(int u,int fa)
{
    int tot=0;
    memset(f2,0,sizeof(f2));
    for(int i=0;i<=siz[u];i++)
    {
        for(int j=0;j<=n-siz[u];j++)
        {
            f2[i+j] = (f2[i+j] + f[u][i] * g[u][j]) % mod;
        }
    }
    for(int v:e[u]) // f[u] = g[v] * F[v]
    {
        if(v == fa) continue;
        memcpy(f1,f2,sizeof(ll)*(n+1));
        int mx=siz[v];
        while(!F[v][mx]) mx--;
        ll inv = qpow(F[v][mx],mod-2);
        for(int i=n;i>=mx;i--)
        {
            if(f1[i])
            {
                ll cnt = f1[i] * inv % mod;
                g[v][i-mx] = cnt;
                for(int j=mx,k=i;j>=0;j--,k--)
                {
                    f1[k] = (f1[k] - (F[v][j] * cnt % mod) + mod) % mod;
                }
            }
        }
        g[v][1] = (g[v][1] + 1) % mod;
    }
    for(int v:e[u])
    {
        if(v == fa) continue;
        dfs1(v,u);
    }
}

int main()
{
    cin >> n;
    for(int i=1,u,v;i<n;i++)
    {
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    g[1][0] = 1;
    dfs1(1,0);
    for(int u=1;u<=n;u++)
    {
        for(int x=0;x<=siz[u];x++)
        {
            for(int y=0;y<=n-siz[u];y++)
            {
                ans[x+y+1] = (ans[x+y+1] + f[u][x] * g[u][y]) % mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout << ans[i] << ' ';
    }
}

:::: 跑的没有 O(n^2) 快，你们有点厉害了qaq