树形 DP：没有上司的舞会

先想清楚为什么非要多这一维。

假设状态只写「g[u] = 以 u 为根的子树的最大快乐和」。现在要合并儿子的结果 —— 可你合不上：u 到底能不能来，取决于它的儿子来没来， 而 g[v] 这个数字里根本没说「v 到底来了没有」。

★ 这就是第 22 章那句话的翻版： 状态里必须带上「后面还要用到的那一点信息」（LIS 那五个字是「以 i 结尾」，这里是「u 来没来」）。

于是：

f[u][0] = 以 u 为根的子树里，u 不来时的最大快乐和
f[u][1] = 以 u 为根的子树里，u 来  时的最大快乐和

转移就自己掉出来了（v 是 u 的儿子）：

f[u][0] = Σ max(f[v][0], f[v][1])      u 不来 → 儿子来不来都行，各挑更大的
f[u][1] = r[u] + Σ f[v][0]             u 来   → 儿子一个都不能来

答案 = max(f[root][0], f[root][1])。

⚠ 注意 f[u][0] 里是 max，不是 f[v][1]。 「上司来了下属就不来」不等于「上司不来下属就必须来」—— 第 12 步会看到这个误解值多少分。

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);                                  // ★ 先把儿子整棵子树算完
        f[u][0] += max(f[v][0], f[v][1]);        // ★ 回来之后才累加
        f[u][1] += f[v][0];
    }
}

★ 那两行累加必须写在 dfs(v) 后面。 写在前面，f[v] 还是初值 0 —— 儿子那棵子树根本还没算。

这就是「依赖谁，就先填谁」在树上的样子。而它有个现成的名字：后序遍历。

好消息是：递归天然帮你把顺序安排好了（第 26 章第 6 步说过同样的话）。 你唯一要做的，就是别把累加写到递归前面去。

切到前序你会看到一个很整齐的画面：每一条线都是红的， 所有 f[u][0] 恒为 0、f[u][1] 恒等于这个人自己的快乐指数。

因为累加发生在 dfs(v) 之前，那时 f[v] 全是 [0, 0]； 而 dfs(v) 又会把 f[v] 整个重写一遍 —— 父亲加过的那份，之后再也没人回头看。

所以整棵树的信息一点都没往上传，最后输出的就是 max(0, r[根])。 默认数据上根是 5 号、快乐指数 2 → 答案 2。

check:viz 用 300 组数据钉死了这条：输出恒等于 max(0, r[根])，一组不差。

f[u][1] 里应该是 Σ f[v][0]（儿子一个都不能来），写成 Σ max(f[v][0], f[v][1]) 之后，「上司来了下属就不来」这条唯一的限制就不存在了。

于是它解的是另一道题：把所有快乐指数为正的人全叫来。 默认数据上 1 + 3 + 2 + 5 + 7 = 18，正好对上。

check:viz 同样用 300 组数据钉死：输出恒等于 Σ max(0, r[i])，一组不差。

连上前面几章，DP 这几章一共钉死了八条这样的恒等式：

前面几章的错误版本都只是「答案不对」。这一章的第三张不一样 —— 它的名单本身就是违规的：会出现一对直接上下级同时到场（画面上是红色虚线）。

它算出来的数最大，可它根本没在解这道题。

答案大不代表答案对。 这也是为什么「输出方案」比「输出一个数」值钱：一个数没法自证清白，一份名单可以。

• 算 f 的时候是后序（先递归再累加）：因为父亲要用儿子的结果；
• 回溯方案的时候是前序（先定自己再定儿子）：因为儿子能不能来，取决于我来没来。

这两个方向都不是背下来的，都是从「谁依赖谁」推出来的 —— 又是同一句话。

check:viz 对这份名单做的是硬验证：名单里不能有任何一对直接上下级， 快乐指数之和必须正好等于那个答案。

gen.cpp 带了四个档位，你可以把当初那几次修改一次一次重跑 （./gen 种子 档位）。种子固定 1..300：

① 加负数（档位 0 → 1）：「以为下属必须来」从 195 涨到 268。 道理很直白 —— 快乐指数全是正数时，「能来就来」本来就划算， 那个错误的理解十有八九恰好取到同一个数。 要抓它，就得造出「这个下属来了反而亏」的局面（第 20 章那条规矩）。

② 打乱编号（档位 1 → 2）：「没找根」从 0 / 300 直接跳到 257 / 300。 这一处改动没有动任何一个数值 —— 没改值域、没改点数、没改形状， 只是把点的编号重新分配了一遍。

★ 这是这一章最值得带走的一条：

数据的随机性不能只在数值上。结构、编号、谁扮演什么角色，同样要随机。

前面几章调的都是数值（第 24 章的 k、第 25 章的容量松紧、第 26 章的堆数）， 这一次那个旋钮根本不在数值里。 写树 / 图的生成器时都要问一句： 我是不是无意中给某个点安排了特殊身份（根、起点、编号 1）？

③ 档位 3 的账要老实算。 它加了「链」和「菊花」两种退化形状，图的是覆盖（第 24 章那条： 参数取到极端时题目会退化成什么样子，那一端也得造）。 但代价是「儿子也能来」的抓获率从 275 掉到 242 —— 如果只看这五个已知 bug，档位 2 更划算。 我还是留了档位 3，因为退化形状防的是还没写出来的那些 bug， 而这五个在两个档位下都抓得住。抓获率是重要指标，但不是唯一指标。

我另写了一份 genRoot1.cpp，和最终档比只改了一处：不打乱编号。 快乐指数照样有负数、形状照样轮着造。同样跑 300 轮：

一个 bug 完全隐身，另外四个纹丝不动。 而且这次原因不用猜： 1 号点确实是根的时候，「找根」和「直接用 1」是同一件事 —— 它压根就没错。

【1】状态里多一维「这个点自己选不选」。 因为父亲能不能选，取决于儿子选没选 —— 而一个光秃秃的「子树最优值」里没有这个信息。 这和第 22 章「以 i 结尾」是同一条道理：状态要带上后面还会用到的那一点信息。

【2】转移在回溯时做，也就是后序遍历。 「依赖谁，就先填谁」第五次登场。好消息是递归天然帮你排好了顺序， 你只要别把累加写到 dfs(v) 前面去 —— 写错了不报错，答案会塌成 max(0, r[根])。

【3】算 f 是后序，回溯方案是前序。 两个方向都是从依赖关系推出来的，不是背的。 而输出方案还有个额外的好处：一份名单可以自证清白，一个数不行 —— 那个「答案 18」的错误版本，名单一画出来就露馅了。

【4】数据的随机性不能只在数值上。 「没找根」这个 bug 在「1 号永远当根」的数据上 0 / 300， 打乱编号之后立刻 257 / 300 —— 而这一处改动没有动任何一个数值。 写树 / 图的生成器时先问：我是不是给某个点安排了特殊身份？