#P18585. Meet in the Middle

Meet in the Middle

Meet in the Middle

有 nn 座城市,编号为 1,…,n1,\ldots,n。城市间有 n−1n-1 条双向公路和 n−1n-1 条双向铁路。只使用公路时,任意两座城市可以互达;只使用铁路时也一样。因此公路网与铁路网分别是一棵带正权的树。

Alice 和 Bob 有 qq 次旅行计划。每次给定两个城市 a,ba,b:Alice 从 aa 出发,只走公路;Bob 从 bb 出发,只走铁路。两人最终到达同一座城市,且各自的路线中不能重复经过某座城市。

你可以选择这座共同的终点城市。求两人的路线长度之和的最大值。

也就是说,每次询问需要计算

$$\max_{1\le v\le n}\bigl(\operatorname{dist}_{\rm road}(a,v)+\operatorname{dist}_{\rm rail}(b,v)\bigr).$$

起点可以相同,终点也可以是某人的起点;不走边的路线长度为0。每次旅行计划独立,两种交通网络和边长始终不变。

输入格式

第一行两个整数 n,qn,q。

接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示一条连接城市 u,vu,v、长度为 ww 的双向公路。

再接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示一条双向铁路,含义相同。

最后 qq 行,每行两个整数 a,ba,b,描述一次旅行计划。

输出格式

对每次询问输出一行一个整数,表示能够达到的最大总路线长度。

数据范围

2≤n≤1052\le n\le10^5,1≤q≤5×1051\le q\le5\times10^5,1≤u,v,a,b≤n1\le u,v,a,b\le n,1≤w≤1091\le w\le10^9。

分别保证公路和铁路构成树。两种网络使用同一套城市编号;相同城市对之间可以同时有公路和铁路,两种边的长度可以不同。输入只有一组数据。

样例输入

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

样例输出

6
4
5
3