Distance Tree(hard version)

 

https://codeforces.com/contest/1632/problem/E2

可以在这个地方阅读

题意

你拥有一棵树,定义其根为 1 号节点,现在你有能力在这棵树中再添加一条边。使得这棵树的最长路径改变。现在你添加的这个边的边权从 1 - n 依次增大,求问,每次增大后加入一条边,使之最长路径的最短距离为多少

思路

首先,我们可以贪心的去思考问题。对于新加入的一个边,如果我们边的其中一个端点是 1 号点的话,那么可保证,最优解中一定存在端点连接 1 号节点的点。

然后,如何寻找的最优解呢。

如果我们在子树中寻找到了一个最长链,我们取其中点,那么我们如果我们链接一条从 1 号点的边到这个点,那么此时,我们的答案便可以分割为两个部分,一个部分是 $\lceil \frac{len}{2}\rceil + x$ , 另一个就是深度,答案是两者中的较大值。

如果我们的深度就是答案,那么也就意味着我们的第一个部分失效了,所以,我们需要一个范围来保证第一个部分可以起到作用。

假若,我们的图如下所示(省去了非关键点)

alt

当我们到达一个节点 lc 的时候,我们得到了如图两个最长分枝。我们得到 depth[y]depth[x],那么此时,我们的 1 连接到节点 x 那么此时,答案便可以变成 $\lceil \frac{len}{2}\rceil + x$ (这里的x不是 x 号节点,是所加边的长度), 其中 len 表示从 yz 之间的距离,也就是 depth[y] + depth[z] - depth[lc] * 2

由于我们此时的答案在小于 yz 的深度的时候才可以起到作用。因此,我们不妨设置一个数组 f 表示,当我们的第一部分生效的时候,我们的范围。我们注意看图,此时我们如果从插入边1-x 上的话。那么我们发现我们的答案最终在 y 或者 z 这个两个点上。如果,我们最终的答案 >= depth[z] 的时候,也就意味着,我在 x 点插入带来的最大值无效,我可以选择在另一个点插入使得 在 y 点的值小于等于此时的 dis[y]。因此,我们的范围最多可以一直生效到 depth[z] - 1 。那么因此我们需要将 f[0 ~ depth[z] - 1] 设置为 max(f[i] , depth[y] + depth[z] - 2 * depth[lc]) 。这里有一个小细节需要注意一下,我们的上面的计算是上取整,因此,我们不妨让这些值 + 1 ,借此来使我们的值变为我们需要的值。

由于遍历 0 ~ depth[z] - 1 耗费的时间过长,我不妨只更新最后一个,然后再完成之后,我们将所有的数组从后向前更新最大值即可。

最终,我们的 f 数组,就可以用一下两个不等式进行表示

  • $ans \ge depth_v$
  • $ans \ge \lceil\frac{f[ans]}{2}\rceil + x$

code

algorithm