CF1632E1 Distance Tree (easy version & hard version)
解题报告。
不一定更好的阅读体验。
E2 没有地方交了所以就交到 E1 了。
震撼挺大的一道题，钦定 \(1\) 为根。
先把 \(x\) 固定下来，连边的一个端点必定为 \(1\) 号点，这样能影响的路径长度最大。
那么现在问题变成，连一条 \(1\to u\) 的边，使得 \(\max(d_v)\) 尽量小。
后面那个完全可以二分一手，设 \(\max(d_u)\le L\)，那么问题变成，是否存在一个 \(u\)，使得添加一条 \(1\to u\) 的边后，\(\max(d_v)\le L\)。
在添加边之前，\(d_v\le L\) 的边不用考虑，只需要考虑 \(\max(d_v)>L\) 的边。
添加 \(1\to u\) 这条边后，影响的是 \(u\) 子树内的点，所以考虑一个 \(u\) 子树内的点 \(v\)，\(d_v\) 变化为 \(x+\operatorname{dis}(u,v)\)。
把这个带入二分答案的式子，可以得到 \(x+\operatorname{dis}(u,v)\le L\)，即 \(\operatorname{dis}(u,v)\le L-x\)，不等式右边可看做常数项，这个不等式成立的条件可看做最远两个点的成立，那么所有点都成立。
所以问题又转化为，添加一条 \(1\to u\) 的边后，\(\max_{1\le v\le n}\{\operatorname{dis}(u,v)\}\) 最小是多少。
推到这个问题时我就不会做了，菜逼。当然你把相应的点拉出来建虚树 E1 就做完了。
下面继续考虑 \(\Theta(1)\) check 这个问题，也就是 E2 做法。
这个其实也很好做，考虑两个点 \(a,b\) 满足 \(d_a>L\land d_b>L\)，且 \(a,b\) 距离 \(D\) 尽可能的大。
那么我们直接将 \(u\) 放到 \(a,b\) 的中点上，然后检查路径长度 \(x+\lceil\dfrac{D}{2}\rceil\) 是否 \(\le L\)，即 \(\lceil\dfrac{D}{2}\rceil\le L-x\)。
这个的正确性很好证明。
采用反证法，假设存在一个点 \(v\) 使得 \(\operatorname{dis}(1,v)>L\)，也就是 \(\operatorname{dis}(u,v)>L-x\ge \lceil\dfrac{D}{2}\rceil\)。
考虑这个式子的实际意义，即，当以 \(u\) 为根时，\(\operatorname{dis}(a,v)=\operatorname{dis}(u,a)+\operatorname{dis}(u,v)>\lceil\dfrac{D}{2}\rceil+\lceil\dfrac{D}{2}\rceil+1\ge D\)，矛盾。
代码实现方面，我们对于二分的 \(L\)，预处理出 \(f_i\) 表示 \(d_j>i\) 的点集距离最大的两点距离，这个倒推做可以做到 \(\Theta(n)\)。
最终复杂度 \(\Theta(n\log n)\)。
标签：Distance,lceil,le,题解,Tree,dfrac,rceil,operatorname,dis From： https://www.cnblogs.com/UperFicial/p/16741006.html