题解：P14254 分割（divide）

xixisuper · 2025-10-18 23:07:12 · 题解

简单计数，感觉没有蓝。

思路

由于 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] 中选择一个点：那么剩下 k-1 个点必须都选择 [r+1,q] 中的点，这时有一个讨论：
  • 如果 [r+1,q] 中多于 k-1 个点，那么 \cap_{i=2}^{k+1} S_i 中的最大值一定大于当前的 t，不满足条件。
  • 如果 [r+1,q] 中正好有 k-1 个点，那么：
  • 如果 [l,r] 中只有一个点，则 S_{k+1} 的最大值一定小于当前的 t，不满足条件。
  • 如果 [l,r] 多于一个点，则满足条件。
  • 如果 [r+1,q] 中少于 k-1 个点，那选鸡毛，不满足条件。
• 从 [l,r] 中选择 x 个点：那么剩下 k-x 个点必须都选择 [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)，瓶颈在于排序。

代码

#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;
}