題意

給定一棵 \(n\) 個點的樹，設(shè)根節(jié)點 \(1\) 的深度為 \(1\)。給定 \(k\)，求有多少從樹中選出 \(k\) 個兩兩不同的節(jié)點，組成有序序列 \(b_1,\cdots,b_k\) 的方案，使得：

• 對于每個 \(1\leq i<k\)，\(1<d_{b_i}\leq d_{b_{i+1}}\)。
• 對于每個 \(b_i\)，斷掉其與父親的連邊，得到 \(k+1\) 個連通塊，設(shè) \(b_i\) 為根的連通塊的 \(d\) 集合為 \(S_i\)，以 \(1\) 為根的連通塊的 \(d\) 集合為 \(S_{k+1}\)，那么需要滿足 \(S_1=\bigcap\limits_{i=2}^{k+1}S_i\)。

答案對 \(998244353\) 取模。\(2\leq k\leq n\leq 10^6\)。

題解

驗題人題解，自認(rèn)為比較自然的思路。

顯然一個連通塊的深度集合是一個區(qū)間 \([l_i,r_i]\)，考慮這些區(qū)間的左端點，第一條限制相當(dāng)于說 \(l_1\leq l_2\leq\cdots\leq l_{k}\)，但第二條限制又說明 \(l_1=\max\limits_{i=2}^{k+1}l_i\)，因此必然有 \(l_1=l_2=\cdots=l_k\)。也就是說選出來的 \(b_i\) 深度必須相同，這啟發(fā)我們對不同深度的點分開來做。

對于每個點 \(u\)，DFS 預(yù)處理出 \(a_u=\max\limits_{v\in sub_u}d_v\)。考慮右端點的限制，設(shè) \(B=\{b_1,\cdots,b_k\}\)，那么第二條限制等價于要求：

接下來設(shè)上式的 \(\min\) 里面前者為 \(X\)，后者為 \(Y\)。

把當(dāng)前深度所有點按 \(a\) 值排序，枚舉 \(a_{b_1}\)，則對于每個 \(a_{b_i}(i>1)\) 都有 \(a_{b_i}\geq a_{b_1}\)。設(shè) \(c_1\) 為 \(a=a_{b_1}\) 的點數(shù)，\(c_2\) 為 \(a>a_{b_1}\) 的點數(shù)。進一步分類討論 \(\min\) 的取值：

• \(a_{b_1}=X\leq Y\)：可以拆成兩條限制：一個是存在 \(b_i(i>1)\) 使得 \(a_{b_i}=a_{b_1}\)，另一個是 \(a\geq a_{b_1}\) 的點沒有全部選完。對于第二條限制，保證 \(c_1+c_2>k\) 即可，對于第一條限制，我們正難則反，用總方案數(shù) \(A_{c_1+c_2-1}^{k-1}\) 減去不合法的方案數(shù) \(A_{c_2}^{k-1}\)。因此若 \(c_1+c_2>k\)，這種 case 合法，答案是 \(c_1(A_{c_1+c_2-1}^{k-1}-A_{c_2}^{k-1})\)。
• \(a_{b_1}=Y<X\)：發(fā)現(xiàn)這是一個很強的限制，對于所有 \(i>1\)，都有 \(a_{b_i}>a_{b_1}\)，且 \(a>a_{b_1}\) 的點要全部選完。注意要讓 \(Y\) 能取到 \(a_{b_1}\) 還需要有 \(c_1\geq 2\)。因此若 \(c_1\geq 2\land k-1=c_2\)，這種 case 合法，答案為 \(c_1\cdot c_2!\)。

時間復(fù)雜度 \(\mathcal{O}(n\log{n})\)，瓶頸在于排序。

代碼

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 5, MOD = 998244353;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
inline void cadd(int &x, int y) { x += y, x < MOD || (x -= MOD); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += MOD); }

int n, k, ans, fa[N], dep[N], mxd[N];
int fac[N], ifac[N];
vector<int> vec[N];

struct AdjList {
	int tot, head[N], nxt[N], to[N];
	inline void ins(int x, int y) { to[++tot] = y, nxt[tot] = head[x], head[x] = tot; }
} T;

inline int qpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
	}
	return res;
}
inline void pre() {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;
	ifac[n] = qpow(fac[n], MOD - 2);
	for (int i = n - 1; ~i; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;
}
inline int A(int n, int m) { return (n < 0 || m < 0 || n < m) ? 0 : (ll)fac[n] * ifac[n - m] % MOD; }
inline void dfs(int x) {
	for (int i = T.head[x]; i; i = T.nxt[i]) {
		int y = T.to[i];
		mxd[y] = dep[y] = dep[x] + 1, dfs(y);
		chk_max(mxd[x], mxd[y]);
	}
	vec[dep[x]].push_back(mxd[x]);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k, pre();
	for (int i = 2; i <= n; ++i) cin >> fa[i], T.ins(fa[i], i);
	dep[1] = 1, dfs(1);
	for (int d = 2; d <= mxd[1]; ++d) {
		sort(vec[d].begin(), vec[d].end());
		int cnt = 0, sum = 0;
		for (int i = 0; i < vec[d].size(); ++i) {
			if (!i || vec[d][i] == vec[d][i - 1]) ++cnt;
			else {
				int cntr = vec[d].size() - sum - cnt;
				if (k < cntr + cnt) cadd(ans, (ll)cnt * sub(A(cntr + cnt - 1, k - 1), A(cntr, k - 1)) % MOD);
				if (cnt >= 2 && k - 1 == cntr) cadd(ans, (ll)cnt * fac[cntr] % MOD);
				sum += cnt, cnt = 1;
			}
		}
		if (k < cnt) cadd(ans, A(cnt, k));
	}
	cout << ans;
	return 0;
}