当前位置: 首页 > news >正文

题解:Luogu P14254 分割(divide)

题意

给定一棵 \(n\) 个点的树,设根节点 \(1\) 的深度为 \(1\)。给定 \(k\),求有多少从树中选出 \(k\) 个两两不同的节点,组成有序序列 \(b_1,\cdots,b_k\) 的方案,使得:

  • 对于每个 \(1\leq i<k\)\(1<d_{b_i}\leq d_{b_{i+1}}\)
  • 对于每个 \(b_i\),断掉其与父亲的连边,得到 \(k+1\) 个连通块,设 \(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\)

题解

验题人题解,自认为比较自然的思路。

显然一个连通块的深度集合是一个区间 \([l_i,r_i]\),考虑这些区间的左端点,第一条限制相当于说 \(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\) 深度必须相同,这启发我们对不同深度的点分开来做。

对于每个点 \(u\),DFS 预处理出 \(a_u=\max\limits_{v\in sub_u}d_v\)。考虑右端点的限制,设 \(B=\{b_1,\cdots,b_k\}\),那么第二条限制等价于要求:

\[a_{b_1}=\min\left(\min_{i=2}^{k}a_{b_i},\max_{u\not\in B}a_u\right) \]

接下来设上式的 \(\min\) 里面前者为 \(X\),后者为 \(Y\)

把当前深度所有点按 \(a\) 值排序,枚举 \(a_{b_1}\),则对于每个 \(a_{b_i}(i>1)\) 都有 \(a_{b_i}\geq a_{b_1}\)。设 \(c_1\)\(a=a_{b_1}\) 的点数,\(c_2\)\(a>a_{b_1}\) 的点数。进一步分类讨论 \(\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\) 即可,对于第一条限制,我们正难则反,用总方案数 \(A_{c_1+c_2-1}^{k-1}\) 减去不合法的方案数 \(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\):发现这是一个很强的限制,对于所有 \(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!\)

时间复杂度 \(\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;
}
http://www.hskmm.com/?act=detail&tid=35330

相关文章:

  • 题解:Luogu P6898 [ICPC 2014 WF] Metal Processing Plant
  • 20251020
  • 32-腾讯IM接入资料和定价
  • 题解:AtCoder ARC207A Affinity for Artifacts
  • 构造单
  • [笔记]高斯消元
  • 半导体设备各细分领域的国内外龙头公司
  • CSP-S 34
  • 02.Python百行代码实现抽奖系统
  • CSP-S 35
  • CSP-S 29
  • 2025网络安全振兴杯wp
  • 10.20每日总结
  • CSP-S 31
  • 后缀树
  • ES原理、zookeeper、kafka
  • CF1606E Arena 题解(动态规划)
  • 服务器CPU市场概况2025
  • CSP-S 24
  • 读书笔记:深入理解java虚拟机
  • CSP-S 19
  • CSP-S 20
  • Flutter应用设置插件 - 轻松打开iOS和Android系统设置
  • CSP-S 22
  • Project. 2025.11化学小组pre
  • MySQLDay1
  • 蛋白表达标签:重组蛋白研究的精妙引擎
  • 106.腾讯地图位置服务再出错
  • 心理咨询系统
  • Adaptive Learning Rate(自适应学习率) - -一叶知秋