一种类型的树贪心
AGC 023 F - 01 on Tree
从根开始往下顺序不太好处理，于是考虑从下往上。
那么就是从叶子开始，向自己的父亲合并，我们对于一个点，它有若干个儿子，假设其中两个叶子儿子分别为 \(x,y\)，然后考虑谁先合并上来更优？显然是颜色为 \(0\) 的先合并。
然后叶子合并完后每个点会变成连通快，我们扩展成连通块 \(x,y\)，记：\(c_{0/1,u}\) 表示 \(u\) 所在连通块的 \(0/1\) 数量。
那么如果先合并 \(x\) 就有：\(c_{1,x}\cdot c_{0,y}< c_{0,x}\cdot c_{1,y}\)，移项就是：\(\frac{c_{1,y}}{c_{0,y}}<\frac{c_{1,x}}{c_{0,x}}\)，那么我们就将所有叶子插入一个优先队列，然后选择这个值最小的，向它的父亲合并即可，用并查集维护 \(c_{0/1,x}\)。然后将父亲插入队列。
这题可以简单点写法，不需要先合并叶子（答案不影响，因为儿子迟早合并上来计算，且计算结果不变），将所有点都插入队列，然后类似 dijkstra，因为一个点合并完之后某个点的父亲点一定比值变小，所以用一个 bool 数组记录一下是否已经合并过了即可。
时间复杂度：\(O(n\log n)\)。
代码
ABC 376 G - Treasure Hunting
确定一个排列 \(q\)，使得树上任意点父亲的位置在这个点前面。
然后要使得以下值最小化：
然后这一题容易发现，还是和上一题类似，要让 \(a\) 序列的顺序对数尽量小即可（接近降序排序）。
这里有两种思路，但是最后代码写法是一样的。
考虑算贡献：
对于某个点的一对儿子 \((x,y)\)，如果先合并 \(x\) 优于先合并 \(y\)，那么就有：
于是并查集维护权值和、大小即可贪心。
考虑转换为上一题
对于 \(a_i\) 这个权值，倒过来排序，直接将 \(a_i\) 视为 \((0,0\dots 0,1)\)，其中有 \(a_i\) 个 \(0\)，然后变成第一道题目。
那么 \(0\) 正好就是权值和，\(1\) 就是大小，按照 \(\frac{c_1}{c_0}\) 排序即可。
最后算答案就是这么合并即可：
时间复杂度：\(O(n\log n)\)。
代码