题解：P14254 分割（divide）

· · 题解

首先发现如果 d_{b_i}>d_{b_1}，那么一定有 d_{b_1}\in S_1，且 d_{b_1}\notin S_i，与题目要求矛盾。又由于 d_{b_i}\ge d_{b_1}，因此所有 d_{b_i} 均相等。

那么先固定 b_1，记 d=d_{b_1}，显然 S_1 即为 b_1 的子树中所有点的深度构成的集合，记 b_1 的子树中最大的深度为 m_{b_1}，则 S_1=[d,m_{b_1}]。接下来要选出与 b_1 深度相同的 b_2,\dots,b_k，同样有 S_i=[d,m_{b_i}]。剩下部分即为原树挖掉这 k 棵子树，设深度为 d 的点组成的集合为 B_d，则 S_{k+1}=\left[1,\max\limits_{b\in B_d-\{b_i\}}\{m_b\}\right]。

此时 S_1=\displaystyle\bigcap_{i=2}^{k+1}S_i 即表示 m_{b_1}=\min\left\{m_{b_i},\max\limits_{b\in B-\{b_i\}}\{m_b\}\right\}。也就是说，m_{b_i}\ge m_{b_1} 且 \max\limits_{b\in B-\{b_i\}}\{m_b\}\ge m_{b_1}，其中至少有一个等号成立。

因此我们知道对于 b\in B_d，至少要有 k+1 棵 m_b\ge m_{b_1} 的子树，同时至少要有另外一个 m_b=m_{b_1}。直接枚举 d 和 m，设 b\in B 且 m_b>m 的 b 有 x 个，m_b=m 的点有 y 个，对这 y 个点中的每个 b_1，都能得到选出 b_2,\dots,b_k 且使得其中至少一个 m_{b_i}=m 的方案数为 A_{x+y-1}^{k-1}-A_{x}^{k-1}，其中 A 为排列数，A_n^m=\dfrac{n!}{(n-m)!}=m!C_n^m。

还有一种情况：所有 m_{b_i} 均大于 m_{b_1}，而\max\limits_{b\in B-\{b_i\}}\{m_b\}=m_{b_1}。这时一定有 x=k-1，对于 y 个 b_1 中的每一个都有 (k-1)! 种方案。

直接 dfs 求出 d 和 m 数组后，预处理阶乘和阶乘逆元即可做到时间空间复杂度 O(n)。

upd：我的实现用到了排序，所以是 O(n\log n) 的。懒得想有没有严格 O(n) 方法了。

Code:

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