社区讨论

本题所有题解复杂度分析疑似错误

YYao_yx
AT_abc311_h[ABC311Ex] Many Illumination Plans参与者 5已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@mjs83k43
此快照首次捕获于
2025/12/30 14:45
2 个月前
此快照最后确认于
2025/12/30 17:20
2 个月前
查看原帖
先简略描述一下官方题解的后半部分：每次 dfs(u,dp) 返回 dpdp 数组和 uu 子树内的 dpdp 数组合并形成的新的 dpdp 数组。然后每次先递归重儿子，再将新的 dpdp 数组向轻儿子递归，这样最后的 dpdp 数组就是完整的 dpdp 数组。而只有 dfs(u,I) 才能表示真正的 uu 子树内的 dpdp 数组。所以每次从根节点往下的一条重链都会是 dfs(u,I)，这样就能每次算出一条重链的 dpdp 值。
官方题解是这样说明复杂度的：设 T(n)T(n) 表示大小为 nn 的树的复杂度，则 T(n)=T(n1)+2∑i=2kT(nk)+O(X)T(n)=T(n_1)+2\sum\limits_{i=2}^kT(n_k)+O(X)。其中 n1≥n2≥⋯≥nkn_1\ge n_2\ge\dots\ge n_k 且 n1+n2+⋯+nk=n−1n_1+n_2+\dots+n_k=n-1。然后说这样是 O(n1+log⁡23X)O(n^{1+\log_23}X) 的。
但实际上我认为这样证明是不对的。官方题解说因为重儿子被递归一遍，轻儿子被递归两遍，所以就有了这样的系数。但是实际上轻儿子是被 递归 一遍，然后再被 遍历 一遍的。
如果不知道我在说什么，那可以先看看官方题解的代码（代码中 g(u)g(u) 为 uu 的儿子的集合，g(u,0)g(u,0) 为 uu 的重儿子）：
CPP
using vl = vector<ll>;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rep1(i, n) for (int i = 1; i < int(n); i++)
void chmax(ll& a, ll b) { a = max(a, b); }
array<vl, 2> dfs(int c, const vl& dp, bool memo) {
  array<vl, 2> Dp;
  if (g[c].empty()) {
    Dp[0] = Dp[1] = dp;
  } else {
    Dp = dfs(g[c][0], dp, memo);
    rep1(i, g[c].size()) rep(t, 2) Dp[t] = dfs(g[c][i], Dp[t], false)[t];
  }
  rep(i, X - W[c] + 1) chmax(Dp[C[c]][i + W[c]], Dp[C[c] ^ 1][i] + B[c]);
  if (memo) {
    rep(i, X - W[c] + 1) chmax(ans[c], Dp[C[c] ^ 1][i] + B[c]);
    rep1(i, g[c].size()) dfs(g[c][i], dp, true);
  }
  return Dp;
}
代码中使用了 dfs(u,dp,o) 表示当前在节点 uu，当前要反悔的数组要与 dpdp 数组合并，当前是 递归 还是 遍历（即当前是否计算答案，计算答案当且仅当在上文所说的重链上）。发现 dpdp 并不影响复杂度，可以设 T(u,0)T(u,0) 表示 dfs(u,*,0) 的复杂度，T(u,1)T(u,1) 表示 dfs(u,*,1) 的复杂度。然后对着官方题解的代码分析复杂度（设 sonuson_u 为 uu 的重儿子，vv 为 uu 的儿子）：
T(u,0)=O(X)+T(sonu,0)+∑v≠sonuT(v,0)=O(X)+∑T(v,0)T(u,0)=O(X)+T(son_u,0)+\sum\limits_{v\neq son_u}T(v,0)=O(X)+\sum T(v,0)
则显然可以推出 T(u,0)=O(X⋅sizu)T(u,0)=O(X\cdot siz_u)。还有 T(u,1)T(u,1)。
T(u,1)=O(X)+T(sonu,1)+∑v≠sonuT(v,0)+∑v≠sonuT(v,1)=O(X)+∑v≠sonuT(v,0)+∑T(v,1)T(u,1)=O(X)+T(son_u,1)+\sum\limits_{v\neq son_u}T(v,0)+\sum\limits_{v\neq son_u}T(v,1)=O(X)+\sum\limits_{v\neq son_u}T(v,0)+\sum T(v,1)
由此可以看出 T(u,0)T(u,0) 就是 遍历 子树，而遍历到一个点的复杂度的代价为 O(X)O(X)。T(u,1)T(u,1) 是 递归 整个子树，然后只 遍历 轻儿子，不 遍历 重儿子。
发现这其实就是启发式合并。而每次合并需要 O(X)O(X) 的代价。时间复杂度 O(nXlog⁡n)O(nX\log n)。如果想官方题解这样说的话启发式合并就变成 O(n1+log⁡23)O(n^{1+\log_23}) 了，显然是不对的。

回复

共 4 条回复，欢迎继续交流。

正在加载回复...