题目内容

某物流公司在一个城市中运营。城市共有 $N$ 个地点，由 $N-1$ 条公路连接，连接的两个地点之间可以通过这些公路到达。物流公司总部设在地点 1。

某一天，一辆物流运输车接到 $M$ 条运输任务。每条任务包含一个寄件地点 $s$ 和一个派送地点 $t$，表示货物需要从 $s$ 收取，之后送往 $t$。

运输车必须按以下两阶段流程完成全部任务。第一阶段：从总部 1 出发，沿公路访问所有寄件地点，收齐全部货物后返回总部 1，并在总部完成扫描。第二阶段：从总部 1 出发，将全部已扫描货物送往各自的派送地点，所有货物送达后返回总部 1，当天工作才算完成。运输任务的执行顺序没有限制。

请计算该物流运输车完成当天全部运输任务所需的最短总行驶路程。

约束条件

• 地点数量 $N$ 不小于 3 且不超过 10^5。
• 运输任务数量 $M$ 不小于 1 且不超过 10^5。
• 每条公路的里程 $c$ 不小于 1 且不超过 10^5。
• 对于每条运输任务，寄件地点 $s$ 和派送地点 $t$ 均为不小于 2 且不大于 $N$ 的整数，并且 $s \neq t$。
• 输入保证所有地点可以通过给出的公路连通。

输入描述

首行包含两个整数 $N$ 和 $M$，分别表示地点数量和运输任务数量。

接下来 $N-1$ 行，每行包含三个整数 $u$、$v$、$c$，表示地点 $u$ 与地点 $v$ 之间有一条里程为 $c$ 的公路。

接下来 $M$ 行，每行包含两个整数 $s$、$t$，依次表示一条运输任务的寄件地点和派送地点。

输出描述

输出一个整数，表示该物流运输车完成当天全部运输任务所需的最短总行驶里程。

样例1

输入

3 1
2 1 1
1 3 5
2 3

输出

12

说明

第一阶段需要前往地点 2 收取货物，一种最优行驶路径为：1 -> 2 -> 1。

返回总部完成扫描后，第二阶段需要将货物送至地点 3，一种最优行驶路径为：1 -> 3 -> 1。

完成全部运输任务的最短总行驶路程为 12。

样例2

输入

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

输出

18

说明

第一阶段需要访问寄件地点 2 和 3，一种最优行驶路径为：1 -> 2 -> 3 -> 2 -> 1。

返回总部完成扫描后，第二阶段需要访问派送地点 3 和 4，一种最优行驶路径为：1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1。

完成全部运输任务的最短总行驶路程为 18。

样例3

输入

7 4
1 2 2
1 3 3
2 4 4
2 5 1
3 6 5
3 7 2
4 6
5 7
6 5
4 7

输出

56

说明

共包含 4 条运输任务。

第一阶段需要访问寄件地点 4、5 和 6，一种最优行驶路径为：1 -> 2 -> 4 -> 2 -> 5 -> 2 -> 1 -> 3 -> 6 -> 3 -> 1。

返回总部并完成货物扫描后，第二阶段需要访问派送地点 5、6 和 7，一种最优行驶路径为：1 -> 2 -> 5 -> 2 -> 1 -> 3 -> 6 -> 3 -> 7 -> 3 -> 1。

所有货物送达并返回总部后，当天运输任务完成，最短总行驶路程为 56。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写