ARC 117 D - Miracle Tree

传送门

绝对值不好搞,想办法拆开。容易想到将结点按 \(E\) 排序,得到序列 \(p\)。

那么限制转化为 \(E_{p_i} - E_{p_{i - 1}}\ge dis_{p_i, p_{i - 1}}\)。

因为 \(dis_{a,b} \le dis_{a,c} + dis_{c,b}\),所以所有限制可以通过将不等式相加得到。

因为要最小,所以大于等于取等于。

那么答案就是 \(1 + \sum_{i = 2}^n dis_{p_i, p_{i - 1}}\)。

需要最小化遍历整个树不用回到起点经过的路径和,贪心的选择一条直径不走两遍,其余的边全都要走两遍即可。

代码

上一篇:Atcoder ARC 117


下一篇:接口测试平台代码实现117:requests优化