证明及优化树上路径求交算法后 将会在洛谷博客上发布
这是一道暑假集训被劝退的神仙题 在今天的信息课上奇迹般地一遍过
根据题意，将某一条边的边权从 $w$ 改为 $0$，即为将经过该条边的路径总长度减去 $w$。而我们要做的，就是改造树上的某一条边，使得最长的路径长度最短。
题目乍一看可以二分，但在这篇题解中采用贪心策略。
首先将所有路径按照长度降序排序。不难发现，只有在“改造”操作能够同时减小前 $x$ 条路径的长度，该操作才是有意义的，否则不会对答案产生贡献。
那么如何使“改造”操作同时减小前 $x$ 条路径的长度呢？显然，此时选取的边一定属于前 $x$ 条路径的交。路径的交一定仍是路径，根据贪心，只需在路径的交上选取最大的边权，将这条边的边权改为 $0$，然后更新答案即可。
仅剩的问题在于如何快速求出前 $x$ 条路径的交。这里介绍一种 tth37 算法。（开始口胡）
引理：路径 $p(u1,v1)$ 与 $p(u2,v2)$ 如果存在交，则路径的交的端点一定为 $lca(u1,u2),lca(u1,v2),lca(v1,u2),lca(v1,v2)$ 中同时属于两条路径的最远点对。
尚未证明。未完待续。