D. 运河环游

Canal Crossing

时间限制：4 秒 · 内存限制：1024 MiB

原题：NWERC 2025 C · 查看官方英文原文（英文 PDF 也已作为本题附件提供）

题目描述

威尼斯有 $n$ 个地点，地点之间有街道和桥梁，均可双向通行。仅使用街道时，所有地点连通，且任意两个地点之间的路线唯一；也就是说，$n-1$ 条街道构成一棵树。每条街道具有给定的正长度，每座桥的长度视为 $0$。

你想选择一个地点作为起点，走完一次环游并回到该起点。环游必须恰好经过每座桥一次，并且每条街道最多经过一次。地点可以重复经过，不要求经过所有街道。

请计算符合条件的最短环游长度。题目保证至少存在一种合法环游。

输入格式

第一行包含 $n$（$3 \leq n \leq 100000$），表示地点数量。

接下来 $n-1$ 行，每行包含 $a$、$b$、$w$（$1 \leq a, b \leq n$，$a \ne b$，$1 \leq w \leq 10^{6}$），表示一条连接 $a$、$b$ 的街道，其长度为 $w$。

随后一行包含 $m$（$1 \leq m \leq 500000$），表示桥梁数量。

接下来 $m$ 行，每行包含 $a$、$b$（$1 \leq a, b \leq n$，$a \ne b$），表示一座连接 $a$、$b$ 的桥。

保证街道构成一棵树；任意一座桥的两个端点之间都没有直接相连的街道；不存在端点对相同的两座桥。

输出格式

输出满足条件的最短环游长度。答案为整数，可能超过 $32$ 位有符号整数的范围。

样例

8
5 1 8
5 2 1
2 7 2
4 2 4
3 1 16
1 6 32
8 4 64
3
7 4
3 6
3 7

45

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

0

原题版权归原作者及相应赛事评委会所有，采用 CC BY-SA 4.0 许可。中文译文为本练习赛整理，按相同许可发布。题号及中文标题作了调整，输入约束、样例和判题要求依照官方原题；图示及完整英文叙述请参阅英文原文附件。