专栏文章

题解：P14254 分割（divide）

VVinstaG173かえで
P14254题解参与者 5已保存评论 5

文章操作

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

当前评论
5 条
当前快照
1 份
快照标识符
@minkms4g
此快照首次捕获于
2025/12/02 03:57
3 个月前
此快照最后确认于
2025/12/02 03:57
3 个月前
查看原文
首先发现如果 dbi>db1d_{b_i}>d_{b_1}，那么一定有 db1∈S1d_{b_1}\in S_1，且 db1∉Sid_{b_1}\notin S_i，与题目要求矛盾。又由于 dbi≥db1d_{b_i}\ge d_{b_1}，因此所有 dbid_{b_i} 均相等。
那么先固定 b1b_1，记 d=db1d=d_{b_1}，显然 S1S_1 即为 b1b_1 的子树中所有点的深度构成的集合，记 b1b_1 的子树中最大的深度为 mb1m_{b_1}，则 S1=[d,mb1]S_1=[d,m_{b_1}]。接下来要选出与 b1b_1 深度相同的 b2,…,bkb_2,\dots,b_k，同样有 Si=[d,mbi]S_i=[d,m_{b_i}]。剩下部分即为原树挖掉这 kk 棵子树，设深度为 dd 的点组成的集合为 BdB_d，则 Sk+1=[1,max⁡b∈Bd−{bi}{mb}]S_{k+1}=\left[1,\max\limits_{b\in B_d-\{b_i\}}\{m_b\}\right]。
此时 S1=⋂i=2k+1SiS_1=\displaystyle\bigcap_{i=2}^{k+1}S_i 即表示 mb1=min⁡{mbi,max⁡b∈B−{bi}{mb}}m_{b_1}=\min\left\{m_{b_i},\max\limits_{b\in B-\{b_i\}}\{m_b\}\right\}。也就是说，mbi≥mb1m_{b_i}\ge m_{b_1} 且 max⁡b∈B−{bi}{mb}≥mb1\max\limits_{b\in B-\{b_i\}}\{m_b\}\ge m_{b_1}，其中至少有一个等号成立。
因此我们知道对于 b∈Bdb\in B_d，至少要有 k+1k+1 棵 mb≥mb1m_b\ge m_{b_1} 的子树，同时至少要有另外一个 mb=mb1m_b=m_{b_1}。直接枚举 dd 和 mm，设 b∈Bb\in B 且 mb>mm_b>m 的 bb 有 xx 个，mb=mm_b=m 的点有 yy 个，对这 yy 个点中的每个 b1b_1，都能得到选出 b2,…,bkb_2,\dots,b_k 且使得其中至少一个 mbi=mm_{b_i}=m 的方案数为 Ax+y−1k−1−Axk−1A_{x+y-1}^{k-1}-A_{x}^{k-1}，其中 AA 为排列数，Anm=n!(n−m)!=m!CnmA_n^m=\dfrac{n!}{(n-m)!}=m!C_n^m。
还有一种情况：所有 mbim_{b_i} 均大于 mb1m_{b_1}，而max⁡b∈B−{bi}{mb}=mb1\max\limits_{b\in B-\{b_i\}}\{m_b\}=m_{b_1}。这时一定有 x=k−1x=k-1，对于 yy 个 b1b_1 中的每一个都有 (k−1)!(k-1)! 种方案。
直接 dfs 求出 dd 和 mm 数组后，预处理阶乘和阶乘逆元即可做到时间空间复杂度 O(n)O(n)。
upd：我的实现用到了排序，所以是 O(nlog⁡n)O(n\log n) 的。懒得想有没有严格 O(n)O(n) 方法了。
Code:
CPP
int n,k,m;
int fa[1000003];
int dep[1000003];
int mxd[1000003];

ll ans;
int c[1000003];
vector<int>d[1000003];
inline void solve(){
	cin>>n>>k;dep[1]=0;
	for(int i=2;i<=n;++i)
		cin>>fa[i];
	for(int i=2;i<=n;++i)
		dep[i]=dep[fa[i]]+1,m=max(m,dep[i]);
	for(int i=n;i>1;--i)
		mxd[i]=max(mxd[i],dep[i]),\
		mxd[fa[i]]=max(mxd[fa[i]],mxd[i]);
	for(int i=1;i<=n;++i)
		++c[dep[i]],d[dep[i]].push_back(mxd[i]);
	for(int i=0;i<=m;++i)
		sort(d[i].begin(),d[i].end());
	for(int i=0,l,r;i<=m;++i){
		for(l=r=c[i]-1;r>=0;r=l){
			while(l>=0&&d[i][l]==d[i][r])--l;
			if(l>=c[i]-1-k)continue;
			if(r-l==1)continue;
			ans=(ans+(A(c[i]-2-l,k-1)-A(c[i]-1-r,k-1)+ntf)*(r-l))%ntf;
			if(c[i]-1-r==k-1)
				ans=(ans+fac[k-1]*(r-l))%ntf;
		}
	}cout<<ans<<"\n";
}

评论

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

正在加载评论...