原题链接
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：
有一棵 nnn 个节点的树，初始时 111 号节点被染黑，其它节点均为白色
允许：
初始时 BBB 在 111 号节点 →\rightarrow→ 间接地说明了 111 号节点是根节点
每一轮，AAA 可以先染黑 kkk 个节点，然后 BBB 可以走到相邻的任意节点，如果 BBB 在白色节点则 BBB 胜，当 AAA 将所有节点染为黑点时则 AAA 胜。
求让 AAA 胜利的最小 kkk
1.3 题目数据范围与猜测
n≤3×105⟶O(n log n)n \le 3 \times 10^5 \longrightarrow O(n~log~n)n≤3×105⟶O(n log n)
1.4 一句话概括题意
有一棵树，求一个最小值使得在游戏规则下 AAA 必胜
2 题目破题推导
2.1 第一步：大拆小，小组大
我们考虑一个节点 uuu 的“威胁”，也就是在 uuu 的子树中，还需要额外染黑的节点数量
* 第一部分：本身欠的（有可能欠负数，也就是不仅可以染孩子，还可以染孩子的子树中需要染黑的）
设 s(i)s(i)s(i) 代表 iii 的子节点数量，则这部分带来的“威胁”值为 s(u)−ks(u) - ks(u)−k
* 第二部分：孩子节点需要补的
设 f(i)f(i)f(i) 表示 iii 的子树中，还需要额外染黑的节点数量，son(i)son(i)son(i) 代表 iii 的所有孩子
则这部分为：∑v∈son(u)max(f(v),0)\sum_{v\in son(u)}max(f(v),0)∑v∈son(u) max(f(v),0)
为什么是 max(f(v),0)max(f(v),0)max(f(v),0)，而不是 f(v)f(v)f(v)？
因为子节点的“威胁”如果是负数，不能用于补充父节点“欠”的，只能补充 vvv 自己的孩子所欠的
3 模型匹配
这题特别重要的一个转换点：
很多时候，我们看到求一个最小值，就理所当然认为这是dp
但是这道题并没有使用dp求这个最小的k
而是使用了二分答案，树形dp只是一个辅助工具
那么我们的dp定义其实和上面的 f(i)f(i)f(i) 一样
然后当我们测试完这个 kkk 后，若 dproot(1)≤0dp_{root(1)}\le 0dproot(1) ≤0，则代表合法
4 最终代码（禁止抄袭，仅用于参考）
