一种类型的树贪心

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\)，使得树上任意点父亲的位置在这个点前面。

然后要使得以下值最小化：

\[\sum_{i=1}^n a_{q_i}\times i \]

然后这一题容易发现，还是和上一题类似，要让 \(a\) 序列的顺序对数尽量小即可（接近降序排序）。

这里有两种思路，但是最后代码写法是一样的。

考虑算贡献：

对于某个点的一对儿子 \((x,y)\)，如果先合并 \(x\) 优于先合并 \(y\)，那么就有：

\[sz_x\cdot sum_y < sz_y\cdot sum_x\\ \frac{sz_x}{sum_x}<\frac{sz_y}{sum_y} \]

于是并查集维护权值和、大小即可贪心。

考虑转换为上一题

对于 \(a_i\) 这个权值，倒过来排序，直接将 \(a_i\) 视为 \((0,0\dots 0,1)\)，其中有 \(a_i\) 个 \(0\)，然后变成第一道题目。

那么 \(0\) 正好就是权值和，\(1\) 就是大小，按照 \(\frac{c_1}{c_0}\) 排序即可。

最后算答案就是这么合并即可：

\[u\to v\\ ans_u = ans_u + ans_v + sz_v\cdot sum_u \]

时间复杂度：\(O(n\log n)\)。

代码