Boruvka 算法

$4$ 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现：

• 当树的形态确定时，我们总是将权值更大的节点安插到深度更小的叶子上。可以将 $a$ 降序排序后逐层填写。
• 一个节点只可能有 $0$ 个或者 $2$ 个儿子。如果只有 $1$ 个儿子，显然可将该节点删除而整棵子树全部向上平移。

设 $f(d,i,c_1,c_2)$ 表示“现在位于第 $d$ 层（此处“层”指的是节点实际深度）。已经填写好了 $a_1,a_2,\cdots,a_i$，且第 $d$ 层共 $c_1$ 个空置（非叶子）节点，第 $d-1$ 层有 $c_2$ 个此类节点”。那么两层的每一空置节点，均会有一个第 $d+1$ 层的儿子。枚举“下一层要填写 $k$ 个元素”，有转移 $$f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1)$$ （更多…）