#P18585. Meet in the Middle
Meet in the Middle
Meet in the Middle
有 座城市,编号为 。城市间有 条双向公路和 条双向铁路。只使用公路时,任意两座城市可以互达;只使用铁路时也一样。因此公路网与铁路网分别是一棵带正权的树。
Alice 和 Bob 有 次旅行计划。每次给定两个城市 :Alice 从 出发,只走公路;Bob 从 出发,只走铁路。两人最终到达同一座城市,且各自的路线中不能重复经过某座城市。
你可以选择这座共同的终点城市。求两人的路线长度之和的最大值。
也就是说,每次询问需要计算
$$\max_{1\le v\le n}\bigl(\operatorname{dist}_{\rm road}(a,v)+\operatorname{dist}_{\rm rail}(b,v)\bigr).$$起点可以相同,终点也可以是某人的起点;不走边的路线长度为0。每次旅行计划独立,两种交通网络和边长始终不变。
输入格式
第一行两个整数 。
接下来 行,每行三个整数 ,表示一条连接城市 、长度为 的双向公路。
再接下来 行,每行三个整数 ,表示一条双向铁路,含义相同。
最后 行,每行两个整数 ,描述一次旅行计划。
输出格式
对每次询问输出一行一个整数,表示能够达到的最大总路线长度。
数据范围
,,,。
分别保证公路和铁路构成树。两种网络使用同一套城市编号;相同城市对之间可以同时有公路和铁路,两种边的长度可以不同。输入只有一组数据。
样例输入
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