lg scp-s模拟赛T2
场上计数的部分调了很久没过。
主要讲一下场上的思路吧，可能有点乱。
首先可以发现每个节点子树的深度集合可以表示成一个上界和一个下界。
下界是节点本身的深度，上界是节点子树里最深的节点的深度。
然后集合的并就相当于对上界取最小，下界取最大。
那我们先选定 \(b_1\)，然后发现选的 \(b\) 序列必须都跟 \(b_1\) 在同一层，不然不能保证下界取到 \(b_1\) 的下界。
接着还需要保证 \(b\) 序列里的数都的上界都需要大于等于 \(b_1\) 的上界，并且其中必须至少有一个 \(b_i\) 的上界等于 \(b_1\) 的上界。
设上界大于 \(b_i\) 的数有 \(t\) 个，等于 \(b_i\) 的有 \(c\) 个，\(c\) 小于 \(2\) 的情况可以直接省去因为选完 \(b_1\) 后集合的并怎么选都并不出 \(b_1\)。
那容斥一下每个 \(b_1\) 的答案就是在 \(t+c-1\) 选 \(k-1\) 个的方案数减去在 \(t\) 中选 \(k-1\) 个的方案数。
所有 \(b_1\) 的总方案数即为 \((A^{k-1}_{t+c-1}-A^{k-1}_{t})*c\)。
场上想到这一步后就开始打代码了，但是发现计数计漏了。
因为还有一种可能的方案是我把上界大于 \(b_1\) 的全选完，这样子最后的并还是可以满足条件。
此时 \(t=k-1\) 并且 \(c>1\)。
最后放上代码：
#include<bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define il inline
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=1e6+1;
const ll mod=998244353;
ll a[2*N],ans;
ll qpow(ll a,ll b){ll res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod,b>>=1;}return res;
}
ll inv(ll x){return qpow(x,mod-2);}
ll C(int n,int m){if(n<m||m<0)return 0;return a[n]*inv(a[n-m])%mod*inv(a[m])%mod;
}
ll A(int n,int m){if(n<m||m<0)return 0;return a[n]*inv(a[n-m])%mod;
}
int n,k,m=1;
int dep[N],mxd[N],fa[N];
vector<int>g[N];
bool cmp(int x,int y){return x>y;}
signed main(){ios;cin>>n>>k,a[0]=1;for(int i=1;i<=2*N-1;i++)a[i]=a[i-1]*i%mod;for(int i=2,f;i<=n;i++){cin>>f;fa[i]=f;}dep[1]=1;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]);g[dep[i]].e_b(mxd[i]);mxd[fa[i]]=max(mxd[fa[i]],mxd[i]);}for(int i=1;i<=m;i++)sort(g[i].begin(),g[i].end(),cmp);for(int i=2;i<=m;i++){int len=g[i].size();for(int j=0;j<len;j++){int t=j,c=1;while(j+1<len&&g[i][j+1]==g[i][j])c++,j++;ll add=0;if(c>1&&c+t>=k+1)add+=A(t+c-1,k-1)-A(t,k-1),add=(add+mod)%mod*c%mod;if(t==k-1&&c>1)add+=a[k-1]*c%mod,add%=mod;ans=(ans+add)%mod;}}cout<<ans;return 0;
}