题解：P14254 分割（divide）

简单计数，感觉没有蓝。

思路

由于

d_{b_i}\le d_{b_{i+1}}

，所以

b_1

的深度一定最浅，但是考虑到如果存在

b_i

满足

d_{b_1}< d_{b_{i}}

，那么

d_{b_1}

一定不属于

S_i

，所以你选择的点的深度一定都是相同的。

我们令

t_u

表示以

u

为根节点的子树中深度最大节点的深度。如果存在

b_i

满足

t_{b_i}<t_1

，则

t_1

一定不属于

S_i

，所以在你选择的点中 $t_1$ 一定是最小的 $t$ 。

于是你可以把每一层的节点按照

t

从小到大排序，我们选点的策略就从

t

相同的每一段来展开，下文中提到的点的编号不是原树上的编号，而是按照 $t$ 排完序后的下标。假设对于第

p

层点来说，该层一共包含

q

个点，且从

l

到

r

的点的

t

值相同：

从 $[l,r]$ $[l, r]$ 中选择一个点：那么剩下 $k-1$ $k - 1$ 个点必须都选择 $[r+1,q]$ $[r + 1, q]$ 中的点，这时有一个讨论：
- 如果 $[r+1,q]$ 中多于 $k-1$ 个点，那么 $\cap_{i=2}^{k+1} S_i$ 中的最大值一定大于当前的 $t$ ，不满足条件。
- 如果 $[r+1,q]$ $[r + 1, q]$ 中正好有 $k-1$ $k - 1$ 个点，那么：
  - 如果 $[l,r]$ 中只有一个点，则 $S_{k+1}$ 的最大值一定小于当前的 $t$ ，不满足条件。
  - 如果 $[l,r]$ 多于一个点，则满足条件。
- 如果 $[r+1,q]$ 中少于 $k-1$ 个点，那选鸡毛，不满足条件。
从 $[l,r]$ $[l, r]$ 中选择 $x$ $x$ 个点：那么剩下 $k-x$ $k - x$ 个点必须都选择 $[r+1,q]$ $[r + 1, q]$ 中的点，这时有一个讨论：
- 如果 $[r+1,q]$ 中有不少于 $k-1$ 个点，那么对答案的贡献为： $\binom{r-l+1}{x}\cdot\binom{q-r}{k-x}\cdot(r-l+1)\cdot(k-1)!$
- 如果 $[r+1,q]$ 中少于 $k-x$ 个点，那选鸡毛，不满足条件。

于是你就做完了，时间复杂度为

O(n\log n)

，瓶颈在于排序。

代码

CPP

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
const ll MOD=998244353;
ll ksm(ll a,ll b){
	ll ret=1;a%=MOD;
	while(b){if(b&1)ret=ret*a%MOD;a=a*a%MOD;b>>=1;}
	return ret;
}
ll jie[N],nijie[N]; 
void init(){
	jie[0]=nijie[0]=1;
	for(ll i=1;i<N;i++){jie[i]=jie[i-1]*i%MOD;nijie[i]=ksm(jie[i],MOD-2);}
}
vector<ll> e[N],dp[N];
inline ll getC(ll x,ll y){return jie[x]*nijie[x-y]%MOD*nijie[y]%MOD;}
ll n,k,x,maxdep,sz[N];
void dfs(ll u,ll dep){
	ll lz=e[u].size();dp[dep].push_back(u);
	sz[u]=dep;maxdep=max(maxdep,dep);
	for(ll i=0;i<lz;i++){dfs(e[u][i],dep+1);sz[u]=max(sz[u],sz[e[u][i]]);}
}
inline bool cmp(ll a,ll b){return sz[a]<sz[b];}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	init();cin>>n>>k;
	for(ll i=2;i<=n;i++){cin>>x;e[x].push_back(i);}dfs(1,0);
	ll ans=0;
	for(ll i=1;i<=maxdep;i++){
		sort(dp[i].begin(),dp[i].end(),cmp);
		ll lz=dp[i].size();
		for(ll beg=0,ed=0;lz-beg>k&&beg<lz;beg=ed+1,ed=beg){
			while((ed+1<lz)&&sz[dp[i][ed+1]]==sz[dp[i][beg]]) ed++;
			for(ll j=1;j<=min(k,ed-beg+1);j++){
				if(j==1){
					if(lz-ed-1!=k-1||beg==ed) continue;
					ans=(ans+(ed-beg+1)*jie[k-1]%MOD)%MOD;
				}
				else{
					if(lz-ed-1<k-j) continue;
					ans=(ans+getC(ed-beg+1,j)*getC(lz-1-ed,k-j)%MOD*j%MOD*jie[k-1])%MOD;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

题解：P14254 分割（divide）

文章操作

思路

代码

相关推荐

评论

题解：P14254 分割（divide）