记 \(dis(T,a,b)\) 为在树 \(T\) 上 \(a,b\) 之间的距离。
给定两棵各 \(n\) 个点的树 \(T_1,T_2\)，\(q\) 次询问，每次给定两个数 \(a,b\)，询问
\[\max_{i=1}dis(T_1,a,i)+dis(T_2,b,i) \]\(1\le n\le 10^5,1\le q\le 5\times 10^5\)
我们对询问离线，在第一棵树上 dfs，枚举 \(a\) 计算询问的答案。
当我们 dfs 到 \(a\) 的时候，我们对于 \(T_2\) 上的每个点 \(i\)，新建一个虚点 \(i'\) 与 \(i\) 连接，边权为 \(dis(T_1,a,i)\)，那么我们只需要在 \(T_2\) 上找距离 \(b\) 最远的点的距离即可。
由于直径的性质，这个点肯定是直径的一个端点，然后我们要维护 \(T_2\) 上直径端点，具体来说维护直径的 \((i,j)\) 和 \(dis(i,i')\) 和 \(dis(j,j')\)，然后合并是简单的。
然后我们对 \(T_1\) 的 dfs 序建出线段树，每个位置维护 \(dis(T_1,a,i)\)，那么每更换一个 \(a\) 就是 \(O(1)\) 次区间虚边边权整体加上/减去一个值，这个不改变这个区间的直径，直接做就好了。
采用 \(O(n\log n)-O(1)\ lca\)，我们就可以在 \(O(n\log n+q)\) 的时间复杂度内解决问题。
口胡老哥，没有代码
标签：le,询问,dfs,CF104160,直径,dis From： https://www.cnblogs.com/Nityacke/p/CF104160.html