完整教程：SCP2025T2：P14254 分割（divide） 题解

P14254 分割（divide）

题面上的 $1\le p_i<i$是不是有问题啊，应该是$1\le p_i\le i$吧，定义为：第$i$个正整数表示结点$(i+1)$的父结点的编号$p_i$。

思路

首先我们记以$i$为根的子树中深度最深的点的深度为$m_i$，则 $S_i=[d_i,m_i]$。可以发现，如果$d_{b_1}<d_{b_i}(1<i\le n)$，那么 $d_{b_1}\notin S_j$，求交集后一定不会满足条件二。故$d_{b_1}=d_{b_2}=\cdots =d_{b_k}$。

我们把深度相同的点放进桶里，针对同一深度的点，从小到大枚举$m_i$ 的值。设 $cnt$ 为相等的 $m_i$ 的个数，$p$ 为比 $m_i$小的值的的个数，$s$ 为比 $m_i$大的值的个数。显然，比$m_i$小的值必然不可能成为被挖去的子树，如果挖去，那么交集后一定不会满足条件二。我们首先钦定一个$m_i$ 为 $b_1$，那么就是在剩下$s+cnt-1$个子树中选择$k-p-1$个挖去，剩下的保留。有问题吗？当然有，倘若所有相等的$m_i$都没有被挖去，且至少有一个比$m_i$大的没有被挖去，那么交集就不满足条件二了，减去这种情况即可。

代码

时间复杂度 $O(n{\log }_{}M)$，其中 $M=998244353$，不过允许优化求逆元的复杂度可以得到$O(n{\log }_{}n)$，懒得改了。

#include<bits/stdc++.h>using namespace std;const int N=1e6+5,mod=998244353;int n,k,dep[N],m[N],jie[N],ni[N];vector<int> a[N],t[N];void dfs(int x){m[x]=dep[x];for(int i=0;i<a[x].size();i++){dep[a[x][i]]=dep[x]+1;dfs(a[x][i]);m[x]=max(m[x],m[a[x][i]]);}t[dep[x]].push_back(m[x]);}int ksm(int x,int y){if(y==1) return x;long long mid=ksm(x,y>>1);if(y&1) return mid*mid%mod*x%mod;else return mid*mid%mod;}int C(int n,int m){if(m==0) return 1;if(n<m||n<0||m<0) return 0;return 1ll*jie[n]*ni[n-m]%mod*ni[m]%mod;}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=2;i<=n;i++){int p;cin>>p;a[p].push_back(i);}jie[0]=1;for(int i=1;i<=n;i++)jie[i]=1ll*jie[i-1]*i%mod,ni[i]=ksm(jie[i],mod-2);//直接用的快速幂求逆元,时间稍微多些dep[1]=1;dfs(1);long long ans=0;for(int i=2;i<=n;i++){sort(t[i].begin(),t[i].end());for(int j=0;j<t[i].size();){int cnt=0,p=j;for(int d=j;d<t[i].size();d++)if(t[i][d]==t[i][j]) cnt++;else break;int s=t[i].size()-j-cnt;long long sum=C(s+cnt-1,k-1);if(s>k-1)sum=(sum-C(s,k-1))%mod;//在s中取k-1个挖去,剩下的给根节点,保证至少给根节点一个ans=(ans+sum*cnt%mod)%mod;//任意一个都可以当b1j+=cnt;}}ans=ans*jie[k-1]%mod;//序列b有序,要乘上排列数ans=(ans+mod)%mod;//涉及减法,可能出现负数cout<<ans;return 0;}