专栏文章

2025_10_27 T3

EEvan_Leo_Azir
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingjsg1
此快照首次捕获于
2025/12/02 02:03
3 个月前
此快照最后确认于
2025/12/02 02:03
3 个月前
查看原文
上位紫，NOIP T4 也完全可以胜任，疑似之前 ZR 集训遇到过，但我并未前去订正，固场上也未做出
考场数据范围为 n≤40n\le40，但时间复杂度实则可以处理至 O(n3)O(n^3)，所以 n≤300n\le 300 完全可以
发现，直接计算相当困难，但是注意到一点，当 n<2×kn < 2\times k 时，会有部分点一直处与联通块中，反之，则起始与最终的 kk 个点交集为空，于是考虑利用此性质分类讨论

n≥2×kn\ge2\times k

观察可得，此时，树的“长相”可以看作两颗大小为 kk 的子树，其中唯一相连一条链（链可能不存在），可以证明，如果中间不是链，则无解，此时的方案数则是两颗子树内部的方案数之积乘二（乘二是因为两棵子树都可以作为起始或最终的 kk 个点）
所以，我们预处理所有可能的子树情况，再将它们拼接
如何预处理？我们先枚举一个根，做 dfs,此时如果该节点子树大小为 kk，就记录下来，至于方案数的计算，可以树形 DP,假设 dpudp_u 表示当前以 uu 为根的子树有 dpudp_u 种方案加/删点（删是加的逆过程，本质方案数一致，这里用删的方式讲解），此时若要合并子树 vv，则
dpu′=dpu×dpv×Csu+sv−1svdp_u'=dp_u\times dp_v\times C_{s_u+s_v-1}^{s_v}
sus_u 指子树大小,以上式子可以这么理解，因为删点本质是找当前树的一个叶子，并进行操作，我们合并子树 vv，其实就是在处理 uu 的操作中，把 处理 vv 的 svs_v 步操作一 一 插入到其中，利用 插板法，就是在 sus_u 个空中（你不能在 uu 之前被删，所以是 sus_u 个空），插入 svs_v 块板子（一个空可以插多块板子）
最后发现，去重后的子树是 O(n)O(n) 量级的,因为对于一个子树而言，它只有一条边连向外部，所以对于一条边顶天只会有 22 棵满足，最终时间复杂度 O(n3w)O(\frac{n^3}{w}) (bitset 判重)

n<k×2n<k\times 2

对于此情况，有一个显然的性质，即：树上有 2×k−n2\times k-n 的点会一直存在且处于同一联通块，接下来为方便描述，我们称这 2×k−n2\times k-n 个点为 BB 类点，其次，观察得，会有 n−kn-k 个点在开始时存在，最后全都被踢出，同时也会有 n−kn-k 个点在开始时都不存在，最后全部加入了联通块中，我们称前者为 AA 类点，后者为 CC 类点
注意到，假设已经确定一 BB 类点，若以此为根，则对于所有根为 A,CA,C 类点的子树，其子树内的点应当同属一组，证明十分简单
所以可以确定，树的重心一定为 BB 类点，考虑反证。因为是重心，以它为根，其儿子们的子树大小 ≤⌊n2⌋\le \lfloor \frac{n}{2} \rfloor，若 重心不为 BB 类，由于 BB 类点联通，则所有 BB 类点都会集中在一棵子树内，此时，以此子树内 BB 组点为根，发现，重心的子树大小一定 ≥⌈n2⌉\ge \lceil \frac{n}{2} \rceil，则无论重心取 AA 类还是 CC 类，由于子树内点为同类点，最后都会得出 A,CA,C 两类点数量 ≥⌈n2⌉\ge \lceil \frac{n}{2} \rceil，即得出 n−k≥⌈n2⌉n-k \ge \lceil \frac{n}{2} \rceil,与前文 n<k×2n < k\times 2矛盾，证毕
因此，我们以重心为根，尝试每次将一个点加入 BB 组，或者把一棵子树加入 A,CA,C 组，因为涉及到加入子树，所以不难想到使用 dfs 序设计一个 DP 状态
dpi,j,pdp_{i,j,p}，表示当前已加入 dfs 序从 ii 到 nn 的点，此时 A,CA,C 类点分别有 j,pj,p 个的方案数，sus_u 表示以 uu 为根的子树大小，preupre_u 表示以 uu 为根子树的内部方案数，转移有
dpi,j,k+=dpi+1,j,p×(n−i+1−j−p)dpi,j+su,k+=dpi+su,j,p×preu×Csu+jsudpi,j,k+su+=dpi+su,j,p×preu×Csu+psudp_{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}
其中 uu 是 dfs 序为 ii 的点
答案显然是 dp1,n−k,n−kdp_{1,n-k,n-k}
preupre_u 可以预处理，时间复杂度 O(n3)O(n^3)
CPP
#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≤40n\le40，以上代码只针对考场的范围，所以未使用 bitset 判重

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...