Difficulty：5.8 6.3 / Easy+ Tag：线段树合并 首先思考暴力怎么做。显然可以枚举每一条边，然后枚举每条路径，如果路径经过这条边，则将长度减去边权；否则不变，求最大值。这样是 O(nmlog⁡n)O(nm\log n)O(nmlogn) 的。 我们可以对每条边的答案拆分成“路径上包括这条边的长度最大值”与“路径中不包括这条边的长度最大值”。可以树剖 O(mlog⁡2n)O(m\log^2 n)O(mlog2n) 完成，还是太劣了。 注意到可以记录所有的查询，然后减去包括这条边的查询就是不包括这条边的查询了。如果有这两颗线段树，可以 O(log⁡m)O(\log m)O(logm) 完成。 然后线段树合并就可以了。 这题特别毒瘤，我加了快读，非递归查询，离散化的方式优化到 1.3s，卡到 1s 就靠你们了（ O(mlog⁡m)O(m\log m)O(mlogm)。