ARC117D 题解

· · 题解

第一步就没想到

可以考虑化简限制。设所有点按 E_i 从小到大排序后顺序是 p_1,p_2,...,p_n。发现只需满足 E_{p_{i+1}} - E_{p_i} \ge \operatorname{dis}(p_i, p_{i+1})。证明是对于任意 i < j < k，若 p_i,p_j 和 p_j,p_k 均满足限制，那么 E_{p_k} - E_{p_i} = E_{p_k} - E_{p_j} + E_{p_j} - E_{p_i} \ge \operatorname{dis}(p_k, p_j) + \operatorname{dis}(p_j, p_i) \ge \operatorname{dis}(p_k, p_i)。

到这里显然每个不等式都可以取等，即 E_{p_{i+1}} = E_{p_i} + \operatorname{dis}(p_i, p_{i+1})，E_{p_n} = 1 + \sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1})。则我们需要找到一个排列 p，使得 \sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1}) 最小。

注意到 \sum\limits_{i=1}^{n-1} \operatorname{dis}(p_i, p_{i+1}) + \operatorname{dis}(p_n, p_1) 最小值为 2(n-1)，这是因为每条边至少经过两次。取到下界也很简单，p 取 dfs 序即可。

现在就变成了要最大化 \operatorname{dis}(p_1, p_n)。p_1,p_n 取直径端点即可。

code