Distance Tree (hard version)

可以在这个地方阅读

题意

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

思路

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

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

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

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

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

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

由于我们此时的答案在小于 y 和 z 的深度的时候才可以起到作用。因此，我们不妨设置一个数组 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 dept{h}_{v}ans\; \backslash ge\; depth\_v$
• $ans\ge \lceil \frac{f[ans]}{2}\rceil +xans\; \backslash ge\; \backslash lceil\backslash frac\{f[ans]\}\{2\}\backslash rceil\; +\; x$

code