#P18308. Packet Transmission
Packet Transmission
Packet Transmission
给定一棵有 个节点的树,表示由路由器和通信信道组成的网络。每个节点是一台路由器,每条边是一条连接两台路由器的信道。第 条边连接 ,沿任一方向通过该信道传输一个数据包均需要 单位时间。
路由器可以存储任意数量的数据包,数据包可以在路由器中等待任意长时间。一台路由器可以同时通过不同的信道发送多个数据包,但一条信道同一时刻至多传输一个数据包,两个方向共用这一限制。一旦开始沿某条边传输,一个数据包必须经过该边所需的完整时间才能到达另一端。
对每次询问,需要从时刻 开始同时完成两个数据包的传输:第一个数据包从 送到 ,第二个数据包从 送到 。可以安排数据包在路由器中等待。请最小化两个数据包到达各自目的地的时刻的最大值,输出这个最小值。
各次询问独立,网络不会被修改。数据包的起点和终点可以相同,此时它在时刻 已到达目的地。数据包同时位于同一台路由器不构成冲突;如果前一个传输恰好结束,下一次传输可以立即开始。
输入格式
第一行包含一个整数 ,表示测试用例数。
对每个测试用例:
- 第一行包含两个整数 。
- 接下来 行,每行包含三个整数 ,描述一条边。
- 接下来 行,每行包含四个整数 ,描述一次询问。
所有边构成一棵树。
输出格式
对每次询问,输出一行一个整数,表示两个数据包都到达目的地所需的最短时间。
数据范围
- 。
- 。
- ,。
- 。
- 。
- 所有测试用例的 之和不超过 , 之和不超过 。
答案可能超过 32 位整数范围。
样例
输入
2
8 3
1 2 3
2 3 5
2 6 7
3 4 4
4 5 3
6 7 2
1 8 6
1 8 2 6
1 5 2 3
5 8 8 5
4 2
1 2 1
2 3 1
3 4 1
1 2 3 4
1 4 2 3
输出
7
15
24
1
3