[NFLS 1457/3] 文件复制 题解

大意

给定一棵树, 树上预先有两个节点被标记, 每个单位时间, 被标记的点可以标记一个相连的点. 求把整课树标记的最小时间.

题解

考虑 dp.

设 $f_u$ 为将 $u$ 标记后, 还需多久将以 $u$ 为根的子树全部标记.

可以贪心处理: 设 $a$ 为 $f_v, v \in son(u)$ 从大到小排序后的结果,

那么 $f_u = a_1 + 1 + a_2 + 2 + ...$

然后将将树看作如下形式:

然后二分最初的点中间的链断开的位置, 分别从两侧转移, 求最大值.

断开的边越靠右, 左侧节点的 $f_{r1}$ 越大, 右侧的 $f_{r2}$ 越小.

而最优方案一定是 $|f_{r2} - f_{r1}|$ 最小, 故二分第一个使得 $f_{r1} > f_{r2}$ 的边即可.