P9167 [省选联考 2023] 城市建造

圆方树 + DP。

首先手玩一下，发现每次必定删去一些联通的点双中所有的点。于是直接考虑圆方树，相当于删除若干联通的方点，使剩下的连通块满足极差小于 $k$。

$k=0$

直接枚举 $n$ 的因数，显然对于 $n$ 的每个因数存在至多一种方案。

考虑不断剥离子树的过程。一个想法是我们总是尝试剥得均匀一些，发现重心一定处于联通的方点之间。于是直接取重心作为根，尝试不断剥离子树。考虑当前节点 $x$：

若为圆点，儿子子树大于 $k$ 就尝试直接剥；否则尝试与 $x$ 划为同一个联通块；
若为方点，则直接尝试剥离子树。

这一部分时间复杂度 $\mathcal O(n\sqrt{n})$。

$k=1$

还是考虑枚举联通块大小，注意到需要计算 $n\operatorname{mod} k\le \frac{n}{k}$ 即可，这样的枚举量是 $\mathcal O(\sqrt{n})$ 的。设 $f(i)$ 表示方案数。

若为圆点，儿子子树大于 $k$ 就尝试直接剥；否则尝试与 $x$ 划为同一个联通块。最后判断与 $x$ 划为同一个联通块的大小。注意与上面不同的是，如果所有儿子都可以被直接剥离，那么我们可以放在任意一个儿子的连通块上。
若为方点，则直接尝试剥离子树。

于是总的时间复杂度为 $\mathcal O(n\sqrt{n})$。感觉有点蠢——其实是我。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10,M=4e5+10,mod=998244353;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,k;
int dfncnt,top,dfn[N],low[N],sta[N];
int gcnt;
vector<int>e[N],g[N];
int rt,si[N],maxp[N];
int f[N];
inline void adj(int &x){x+=x>>31&mod;}
inline void add_e(int u,int v)
{
    e[u].push_back(v);
    e[v].push_back(u);
}
inline void add_g(int u,int v)
{
    g[u].push_back(v);
    g[v].push_back(u);  
}
inline void build(int x,int y)
{
    ++gcnt;
    for(int u=0;u!=y;--top)u=sta[top],add_g(u,gcnt);
    add_g(x,gcnt);
}
void Tarjan(int x)
{
    dfn[x]=low[x]=++dfncnt;
    sta[++top]=x;
    for(auto y:e[x])
    {
        if(!dfn[y])
        {
            Tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]==low[y])build(x,y);
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void getrt(int x,int fa)
{
    si[x]=x<=n,maxp[x]=0;
    for(auto y:g[x])
    {
        if(y==fa)continue;
        getrt(y,x);
        si[x]+=si[y];
        maxp[x]=max(maxp[x],si[y]);
    }
    maxp[x]=max(maxp[x],n-si[x]);
}
bool dfs0(int x,int fa,int k)
{
    if(si[x]<k)return 0;
    if(x<=n)
    {
        if(si[x]==k)return 1;
        int sum=1;
        for(auto y:g[x])
        {
            if(y==fa)continue;
            if(si[y]<k)sum+=si[y];
            else if(!dfs0(y,x,k))return 0;
        }
        return sum==k;
    }
    for(auto y:g[x])
    {
        if(y==fa)continue;
        if(!dfs0(y,x,k))return 0;
    }
    return 1;
}
void dfs1(int x,int fa,int k)
{
    if(si[x]<k)return f[x]=0,void();
    if(x<=n)
    {
        f[x]=0;
        int sum=1,res=1,cnt=0;
        for(auto y:g[x])
        {
            if(y==fa)continue;
            dfs1(y,x,k);
            if(si[y]<k)sum+=si[y];
            if(si[y]==k)f[y]?cnt++:sum+=si[y];
            if(si[y]>k)res=1ll*res*f[y]%mod;
        }
        if(k<=sum&&sum<=k+1)f[x]=res;
        if(sum==1)adj(f[x]+=1ll*res*cnt%mod-mod);
        return ;
    }
    f[x]=1;
    for(auto y:g[x])
    {
        if(y==fa)continue;
        dfs1(y,x,k);
        f[x]=1ll*f[x]*f[y]%mod;
    }
}
inline int solve0()
{
    int res=0;
    for(int i=1;i<n;i++)res+=(n%i==0&&dfs0(rt,0,i));
    return res;
}
inline int solve1()
{
    int res=0;
    for(int i=1;i<n;i++)
        if(n%i<=n/i)
        {
            dfs1(rt,0,i),adj(res+=f[rt]-mod);
        }
    return res;
}
int main()
{
    freopen("cities.in","r",stdin);
    freopen("cities.out","w",stdout);
    read(n,m,k);
    gcnt=n;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u,v);
        add_e(u,v);
    }
    Tarjan(1),top--;
    getrt(1,0);
    rt=1;
    for(int i=1;i<=n;i++)if(maxp[i]<maxp[rt])rt=i;
    getrt(rt,0);
    if(!k)printf("%d\n",solve0());
    else printf("%d\n",solve1()-solve0());
    return 0;
}