2025_10_27 T3

Evan_Leo_Azir · 2025-10-29 21:12:21 · 题解

上位紫，NOIP T4 也完全可以胜任，疑似之前 ZR 集训遇到过，但我并未前去订正，固场上也未做出

考场数据范围为 n\le40，但时间复杂度实则可以处理至 O(n^3)，所以 n\le 300 完全可以

发现，直接计算相当困难，但是注意到一点，当 n < 2\times k 时，会有部分点一直处与联通块中，反之，则起始与最终的 k 个点交集为空，于是考虑利用此性质分类讨论

n\ge2\times k

观察可得，此时，树的“长相”可以看作两颗大小为 k 的子树，其中唯一相连一条链（链可能不存在），可以证明，如果中间不是链，则无解，此时的方案数则是两颗子树内部的方案数之积乘二（乘二是因为两棵子树都可以作为起始或最终的 k 个点）

所以，我们预处理所有可能的子树情况，再将它们拼接

如何预处理？我们先枚举一个根，做 dfs,此时如果该节点子树大小为 k，就记录下来，至于方案数的计算，可以树形 DP,假设 dp_u 表示当前以 u 为根的子树有 dp_u 种方案加/删点（删是加的逆过程，本质方案数一致，这里用删的方式讲解），此时若要合并子树 v，则

dp_u'=dp_u\times dp_v\times C_{s_u+s_v-1}^{s_v}

最后发现，去重后的子树是 $O(n)$ 量级的,因为对于一个子树而言，它只有一条边连向外部，所以对于一条边顶天只会有 $2$ 棵满足，最终时间复杂度 $O(\frac{n^3}{w})$ (bitset 判重) #### $n<k\times 2

对于此情况，有一个显然的性质，即：树上有 2\times k-n 的点会一直存在且处于同一联通块，接下来为方便描述，我们称这 2\times k-n 个点为 B 类点，其次，观察得，会有 n-k 个点在开始时存在，最后全都被踢出，同时也会有 n-k 个点在开始时都不存在，最后全部加入了联通块中，我们称前者为 A 类点，后者为 C 类点

注意到，假设已经确定一 B 类点，若以此为根，则对于所有根为 A,C 类点的子树，其子树内的点应当同属一组，证明十分简单

所以可以确定，树的重心一定为 B 类点，考虑反证。因为是重心，以它为根，其儿子们的子树大小 \le \lfloor \frac{n}{2} \rfloor，若重心不为 B 类，由于 B 类点联通，则所有 B 类点都会集中在一棵子树内，此时，以此子树内 B 组点为根，发现，重心的子树大小一定 \ge \lceil \frac{n}{2} \rceil，则无论重心取 A 类还是 C 类，由于子树内点为同类点，最后都会得出 A,C 两类点数量 \ge \lceil \frac{n}{2} \rceil，即得出 n-k \ge \lceil \frac{n}{2} \rceil,与前文 n < k\times 2矛盾，证毕

因此，我们以重心为根，尝试每次将一个点加入 B 组，或者把一棵子树加入 A,C 组，因为涉及到加入子树，所以不难想到使用 dfs 序设计一个 DP 状态

$$ dp_{i,j,k}+=dp_{i+1,j,p}\times(n-i+1-j-p)\\ dp_{i,j+s_u,k}+=dp_{i+s_u,j,p}\times pre_u \times C_{s_u+j}^{s_u}\\ dp_{i,j,k+s_u}+=dp_{i+s_u,j,p}\times pre_u\times C_{s_u+p}^{s_u} $$ 其中 $u$ 是 dfs 序为 $i$ 的点答案显然是 $dp_{1,n-k,n-k}

pre_u$ 可以预处理，时间复杂度 $O(n^3)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=4e1+5,Mod=1e9+9;
int n,k,cnte,cntn,dfn,ans,root,mins;
int head[maxn],mul[maxn],inv[maxn],f[maxn];
int siz[maxn],dep[maxn],dp[maxn][maxn>>1][maxn>>1],pre[maxn],rk[maxn];
ll nod[maxn];
struct EDGE{
    int v,nxt;
}e[maxn<<1];
struct TREE{
    int rot,res,siz;
    ll nod;
}tree[maxn<<1];
map<ll,bool>p;
void adde(int u,int v)
{
    e[cnte]={v,head[u]};
    head[u]=cnte++;
}
int read()
{
    int ret=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*w;
}
int add(int x,int y) {return x+y>=Mod?x+y-Mod:x+y;}
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1) ret=1ll*ret*x%Mod;
        x=1ll*x*x%Mod;
        y>>=1;
    }
    return ret;
}
int com(int x,int y) {return 1ll*mul[y]*inv[x]%Mod*inv[y-x]%Mod;}
void pre_all()
{
    mul[0]=1;
    for(int i=1;i<maxn;i++) mul[i]=1ll*mul[i-1]*i%Mod;
    inv[maxn-1]=qpow(mul[maxn-1],Mod-2);
    for(int i=maxn-2;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
}
void dfs1(int u,int fa)
{
    nod[u]=1ll<<(u-1),f[u]=1,siz[u]=1;
    for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fa)
    {
        dfs1(to,u);
        nod[u]|=nod[to],f[u]=1ll*f[u]*f[to]%Mod*com(siz[to],siz[u]+siz[to]-1)%Mod;
        siz[u]+=siz[to];
    }
    if(!p[nod[u]]&&siz[u]==k)
    {
        p[nod[u]]=1;
        tree[++cntn]={u,f[u],siz[u],nod[u]};
    }
}
void dfs2(int u,int fa)
{
    dep[u]=dep[fa]+1;
    for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fa) dfs2(to,u);
}
void inpu()
{
    n=read(),k=read();
    memset(head,-1,sizeof(head));
    for(int i=1,u,v;i<n;i++)
    {
        u=read(),v=read();
        adde(u,v);adde(v,u);
    }
}
void deal() {ans=mul[n];}
void deal1()
{
    for(int i=1;i<=n;i++) dfs1(i,0);
    for(int i=1;i<cntn;i++)
    {
        dfs2(tree[i].rot,0);
        for(int j=i+1;j<=cntn;j++) if(!(tree[i].nod&tree[j].nod))
        {
            if(dep[tree[j].rot]+tree[i].siz+tree[j].siz-2!=n) continue;
            ans=add(ans,1ll*tree[i].res*tree[j].res%Mod);
        }
    }
    ans=2ll*ans%Mod;
}
void getroot(int u,int fa)
{
    int ma=0;
    siz[u]=1;
    for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fa)
    {
        getroot(to,u);
        siz[u]+=siz[to],ma=max(ma,siz[to]);
    }
    ma=max(ma,n-siz[u]);
    if(!root||ma<mins) root=u,mins=ma;
}
void dfs_pre(int u,int fa)
{
    pre[u]=siz[u]=1,rk[++dfn]=u;
    for(int i=head[u],to;i!=-1;i=e[i].nxt) if((to=e[i].v)!=fa)
    {
        dfs_pre(to,u);
        pre[u]=1ll*pre[u]*pre[to]%Mod*com(siz[to],siz[u]+siz[to]-1)%Mod;
        siz[u]+=siz[to];
    }
}
void deal2()
{
    getroot(1,0);
    dfs_pre(root,0);
    dp[n+1][0][0]=1;
    for(int i=n;i>=1;i--) for(int j=0;j<=n-k;j++) for(int p=0;p<=n-k;p++)
    {
        int u=rk[i];
        if(n-i+1>=j+p) dp[i][j][p]=add(dp[i][j][p],1ll*dp[i+1][j][p]*((n-i+1)-j-p)%Mod);
        if(j+siz[u]<=n-k) dp[i][j+siz[u]][p]=add(dp[i][j+siz[u]][p],1ll*dp[i+siz[u]][j][p]*pre[u]%Mod*com(siz[u],siz[u]+j)%Mod);
        if(p+siz[u]<=n-k) dp[i][j][p+siz[u]]=add(dp[i][j][p+siz[u]],1ll*dp[i+siz[u]][j][p]*pre[u]%Mod*com(siz[u],siz[u]+p)%Mod);
    }
    ans=dp[1][n-k][n-k];
}
void solve()
{
    inpu();
    if(k==1) deal();
    else if((k<<1)<=n) deal1();
    else deal2();
    printf("%d",ans);
}
int main()
{
    pre_all();
    int t=1;
    while(t--) solve();
    return 0;
}

2025_11_5 注：由于考场数据为 n\le40，以上代码只针对考场的范围，所以未使用 bitset 判重