P15831 [JOI Open 2015] 选举活动 / Election Campaign

在 JOI 共和国中，有 $N$ 座城市，编号从 1 到 $N$。这些城市由 $N-1$ 条道路连接。JOI 共和国的人民使用这些道路在城市间旅行。每条道路均可双向通行。通过一条或多条道路，人们可以在任意两座城市之间往来。 IOI 先生是 JOI 共和国总统的候选人。当然，为了成为总统，他必须进行总统竞选活动。他的秘书为他制定了 $M$ 个竞选计划。在第 $i$ 个计划中，IOI 先生将从城市 $A_i$ 出发，沿着最短路径（即经过最少道路）前往城市 $B_i$，并在沿途的每一座城市（包括城市 $A_i$ 和城市 $B_i$）发表公开演讲。由于他的秘书非常出色，已知如果执行第 $i$ 个计划，IOI 先生将获得 $C_i$ 张选票。多个计划可以同时执行。 然而，JOI 共和国的人民没有耐心。如果 IOI 先生在同一座城市发表演讲超过一次，他将失去 JOI 共和国人民的支持。 由于 IOI 先生想成为总统，他希望获得尽可能多的选票。你是 JOI 共和国的超级程序员，因此他请你编写一个程序，在假设他不会在同一座城市发表演讲超过一次的前提下，计算他在总统选举中能获得的最大选票数。 ### 任务 给定 JOI 共和国的城市数量 $N$、道路信息、竞选计划的数量 $M$ 以及每个计划的信息，编写一个程序计算 IOI 先生在总统选举中能获得的最大选票数。

从标准输入读取以下数据。 - 输入的第一行包含一个整数 $N$，表示 JOI 共和国的城市数量。 - 接下来的 $N-1$ 行中，第 $i$ 行（$1 \leq i \leq N-1$）包含两个以空格分隔的整数 $X_i, Y_i$。这表示第 $i$ 条道路连接城市 $X_i$ 和城市 $Y_i$。 - 接下来的一行包含一个整数 $M$，表示竞选计划的数量。 - 接下来的 $M$ 行中，第 $i$ 行（$1 \leq i \leq M$）包含三个以空格分隔的整数 $A_i, B_i, C_i$。这表示在第 $i$ 个计划中，IOI 先生将从城市 $A_i$ 沿着最短路径前往城市 $B_i$，如果执行该计划，他将获得 $C_i$ 张选票。

输出应包含一行，其中包含一个整数，表示 IOI 先生在总统选举中能获得的最大选票数。

### 样例 1 解释 在此样例输入中，最优策略是执行计划 1 和计划 3。 ### 样例 2 解释 此样例输入满足子任务 3 的约束条件。 ### 样例 3 解释 此样例输入满足子任务 4 的约束条件。 ### 约束条件 所有输入数据满足以下条件。 - $2 \leq N \leq 100\,000$。 - $1 \leq X_i \leq N$。 - $1 \leq Y_i \leq N$。 - $X_i \ne Y_i$（$1 \leq i \leq N-1$）。 - 人们可以通过一条或多条道路在任意两座城市之间往来。 - $1 \leq M \leq 100\,000$。 - $1 \leq A_i \leq N$。 - $1 \leq B_i \leq N$。 - $A_i \ne B_i$（$1 \leq i \leq M$）。 - $1 \leq C_i \leq 10\,000$。 ### 子任务 #### 子任务 1 [10 分] - $M \leq 15$。 #### 子任务 2 [5 分] - $X_i = i$（$1 \leq i \leq N-1$）。 - $Y_i = i+1$（$1 \leq i \leq N-1$）。 - $C_i = 1$（$1 \leq i \leq M$）。 #### 子任务 3 [5 分] - $X_i = i$（$1 \leq i \leq N-1$）。 - $Y_i = i+1$（$1 \leq i \leq N-1$）。 #### 子任务 4 [30 分] - $C_i = 1$（$1 \leq i \leq M$）。 #### 子任务 5 [10 分] - $N \leq 1\,000$。 - $M \leq 1\,000$。 #### 子任务 6 [40 分] - 无额外约束。 翻译由 DeepSeek V3.2 完成