[HNOI/AHOI2018] 排列

首先将原题题意转化为，构造排列 $p$，要求在有根树上如果 $u$ 是 $v$ 的父亲，则 $p_u<p_v$。

最大化 $\sum p_iw_i$ 的值。

从极端情况入手，考察树上权值最小的非根点 $u$，不难发现它在排列上紧随其父亲 $f$ 之后（即 $p_u=p_f+1$）一定不劣。于是我们便可以将 $f$ 和 $u$ 作为一个连续段考察。具体来说是将两个权值放进一个节点中，新节点的儿子为 $u$ 的所有儿子和 $f$ 除了 $u$ 之外的儿子，新节点的父亲为 $f$ 的父亲。

那么我们不免想到，经过第一次合并后整个序列是否能够按照类似的方式继续贪心地合并呢？

我们考察一个平均权值最小的连续段 $u_1,u_2,\cdots,u_s$，证明它在排列上紧随其父亲之后一定不劣。

考虑一种它没有紧随其父亲之后的方案，假设它前面一个连续段为 $v_1,v_2,\cdots,v_r$，$v$ 前面排列里有 $p$ 个数，我们交换 $u,v$ 所带来的答案增量为

$$\displaylines{\begin{aligned} \Delta&=\left(\sum_{i=1}^s(p+i)u_i+\sum_{i=1}^r(p+i+s)v_i\right)-\left(\sum_{i=1}^r(p+i)v_i+\sum_{i=1}^s(p+i+r)u_i\right)\\ &=s\sum_{i=1}^rv_i-r\sum_{i=1}^su_i\\ &=rs\left(\frac{\sum_{i=1}^rv_i}r-\frac{\sum_{i=1}^su_i}s\right)\\ &\ge0 \end{aligned} }$$

由此可得，如果 $u$ 前面不紧邻父亲，那么交换它与它前面的连续段之后一定不劣。

此时做法已经呼之欲出——用数据结构维护所有可合并连续段，每次找到平均权值最小的，将它和父亲合并，同时维护连续段内贡献。