题目
给出一棵带边权的树,求一个排列\(p\),使得\(\sum_{i=1}^{n}{dis(i, p_i)}\)的值最大,其中\(dis(v, u)\)表示\(v\)到\(u\)的距离。
算法
这题的思路非常巧妙,又是和重心有关的题目!记得ydc的大树这题的ydc的做法有异曲同工之妙。
首先我们列答案的计算公式:\[\sum_{i=1}^{n}{dep_i+dep_{p_i}-dep_{lca(i,p_i)}}\]
其中\(dep(i)\)是\(i\)到根的距离,\(lca(v,u)\)就不用说了吧。
上面的式子等价于\[2 \sum_{i=1}^{n}{p_i}-\sum_{i=1}^{n}{dep_{lca(i,p_i)}}\]
我们就要使\(\sum_{i=1}^{n}{dep_{lca(i,p_i)}}\)最小化。
找到树的重心\(root\),并使它 变为根,显然我们有一种方法,使得\(lca(i,p_i)\)都是\(root\),所以答案就是\(2 \sum_{i=1}^{n}{p_i}\)。
难点在求字典序最小的排列\(p\)。
我们可以按\(1\)到\(n\)的顺序依次确定\(p_i\),根据贪心,我们每次必然选标号最小的点\(j\)。而且这个点要满足:
- \(lca(i,j)=root\),我们可以把\(root\)去掉,那么一棵树就裂成了若干“小树”,那么就是要满足\(i\)和\(j\)不在同一个小树。
- 仅仅满足上面的条件是不够的,因为有可能出现\(i\)和\(j\)只能在同一个小树的情况,所以我们要稍加限制:如果某个小树里出现了
标号大于i的结点数量
+还没有被选的结点数量
=\(n-i\),那么,\(i\)或\(j\)之一 一定要在这个小树里。