题解：P16309 [ICPC 2023 Jinan R] 图划分 2

lailai0916 · 2026-08-31 06:04:40 · 题解

题意简述

删除树上的若干条边。 要求每个剩余连通块的大小都是 k 或 k+1。

求不同删边方案的数量。

解题思路

将树根定为 1。 先考虑常规的树形动态规划。

记 f_{u,s} 表示处理完 u 的子树后， 所有已经封闭的连通块均合法， 而包含 u 的未封闭连通块大小为 s。

这个连通块还可能通过父边继续扩大。 因此，只需保留 1\le s\le k+1 的状态。

设当前状态为 x， 儿子 v 的状态为 y。

若保留边 (u,v)，两个未封闭块会合并。 仅当 x+y\le k+1 时合法，转移为：

若删除边 (u,v)， 儿子一侧的连通块必须立即封闭。 所以，只允许 y=k 或 y=k+1：

直接对每个节点执行稀疏背包已经可以通过。 但大量单儿子链仍会重复搬运相同状态。 下面进一步压缩这些转移。

若儿子 v 的子树大小小于 k， 这棵子树不可能独立形成合法连通块。 因此，边 (u,v) 必须保留， 且 v 的整棵子树都属于 u 的未封闭块。

这类节点无需建立动态规划数组。 它们只通过子树大小参与最近保留祖先的强制重量。

只保留子树大小至少为 k 的节点关系。 对其中每个节点 u，定义强制重量：

这些小子树以后无需单独参与背包。 若某个 w_u>k+1， 包含 u 的连通块已经超过允许大小， 且后续合并无法使它缩小，因此不存在合法方案。

所有强制重量覆盖的原树节点互不重复。 所以：

若 u 没有保留下来的儿子， 它只有状态 f_{u,w_u}=1。

若 u 恰有一个保留下来的儿子 v， 转移可以直接写成：

同时，切断儿子边会产生额外状态：

使用 deque 保存整段状态。 向前补 w_u 个零并删去末尾， 就完成了平移与超过 k+1 的截断。

由于所有 w_u 之和不超过 n， 全部单儿子链的转移总计只需 O(n) 时间。

若 u 有至少两个保留下来的儿子， 才执行真正的背包合并。 合并时只枚举两个数组中的非零位置， 并使用开头给出的保留边与删除边转移。

代码先迭代求出父亲、遍历顺序与子树大小。 再按逆序计算动态规划，避免递归栈溢出。

最后，根节点的连通块也必须封闭。 答案为：

下面说明分叉处背包的总代价。

一个状态的可能大小数量至多为：

设一次合并两侧的子树规模为 x,y。 忽略常数后，枚举量不超过：

若两侧都至少为 k^2， 这种合并不超过 O(n/k^2) 次。 每次至多花费 O(k^2)，总计 O(n)。

若一次合并使累计规模首次达到 k^2， 代价不超过较小一侧的规模。 每个节点只会参与一次这样的跨界， 总计仍为 O(n)。

其余合并都位于规模小于 k^2 的极大子树内。 对规模为 z 的一棵子树， 普通树上背包的乘积和为 O(z^2)。 除以 k^2 后得到 O(z)。 这些极大子树互不相交，总计也是 O(n)。

另外，分叉节点的儿子数量之和为 O(n/k)。 每次扫描长度为 k+2 的状态数组， 总计仍为 O(n)。

因此，时间复杂度与空间复杂度都是 O(n)。

参考代码

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

using ll=long long;
using pii=pair<int,int>;
const int N=100005;
const int mod=998244353;
vector<int> G[N],buf;
vector<pii> x,y;
deque<int> f[N];
int fa[N],siz[N],ord[N];
void merge(deque<int> &a,deque<int> &b,int k)
{
    x.clear();
    y.clear();
    for(int i=1;i<=k+1;i++)
    {
        if(a[i])x.push_back({i,a[i]});
        if(b[i])y.push_back({i,b[i]});
    }
    fill(buf.begin(),buf.end(),0);
    int cut=(b[k]+b[k+1])%mod;
    for(auto [i,p]:x)
    {
        buf[i]=(buf[i]+(ll)p*cut)%mod;
        for(auto [j,q]:y)
        {
            if(i+j>k+1)break;
            buf[i+j]=(buf[i+j]+(ll)p*q)%mod;
        }
    }
    a.assign(buf.begin(),buf.end());
    deque<int>().swap(b);
}
void solve()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int cnt=1;
    ord[1]=1;
    fa[1]=0;
    for(int i=1;i<=cnt;i++)
    {
        int u=ord[i];
        for(int v:G[u])
        {
            if(v==fa[u])continue;
            fa[v]=u;
            ord[++cnt]=v;
        }
    }
    for(int i=n;i;i--)
    {
        int u=ord[i];
        siz[u]++;
        if(fa[u])siz[fa[u]]+=siz[u];
    }
    buf.resize(k+2);
    bool ok=1;
    for(int i=n;i&&ok;i--)
    {
        int u=ord[i],s=1,c=0,v=0;
        if(siz[u]<k)continue;
        for(int j:G[u])if(fa[j]==u)
        {
            if(siz[j]<k)s+=siz[j];
            else{c++;v=j;}
        }
        if(s>k+1)
        {
            ok=0;
            break;
        }
        if(!c)
        {
            f[u].assign(k+2,0);
            f[u][s]=1;
        }
        else if(c==1)
        {
            int z=(f[v][k]+f[v][k+1])%mod;
            f[u]=move(f[v]);
            for(int j=0;j<s;j++)
            {
                f[u].push_front(0);
                f[u].pop_back();
            }
            f[u][s]=(f[u][s]+z)%mod;
        }
        else
        {
            f[u].assign(k+2,0);
            f[u][s]=1;
            for(int j:G[u])if(fa[j]==u&&siz[j]>=k)merge(f[u],f[j],k);
        }
    }
    int ans=ok?(f[1][k]+f[1][k+1])%mod:0;
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++)
    {
        G[i].clear();
        deque<int>().swap(f[i]);
        siz[i]=0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}