题目描述

译自 JOI Open 2015 T2 「選挙運動 / 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}$ 票。IOI 先生可以执行多个计划。

然而，JOI 共和国的人民很没有耐心。如果 IOI 先生在同一个城市发表多次公开演讲，他将失去 JOI 共和国人民的支持。

IOI 先生想成为总统，所以他想得到尽可能多的选票。由于你是 JOI 共和国的超级程序员，他请你写一个程序，计算在他不会在同一个城市发表多次公开演讲的情况下，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 先生在总统选举中可以获得的最大票数。

7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8

19

在这个样例中，最优的策略是执行计划 $1$ 和计划 $3$ 的竞选活动。

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11

18

这个样例满足子任务 3 的限制。

10
10 6
2 7
1 9
9 8
3 8
6 4
7 8
5 4
4 8
7
1 3 1
4 10 1
2 8 1
5 3 1
3 7 1
8 5 1
1 9 1

3

这个样例满足子任务 4 的限制。

20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204

29191

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$
• $1 \leq X_{i} \leq N$
• $1 \leq Y_{i} \leq N$
• $X_{i} \neq Y_{i}\ (1 \leq i \leq N-1)$
• 人们可以通过一条或多条道路在任意两个城市之间旅行
• $1 \leq M \leq 10^5$
• $1 \leq A_{i} \leq N$
• $1 \leq B_{i} \leq N$
• $A_{i} \neq B_{i}\ (1 \leq i \leq M)$
• $1 \leq C_{i} \leq 10000$

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$M \leq 15$	$10$
$2$	$X_{i}=i,Y_{i}=i+1$；$C_{i}=1$	$5$
$3$	$X_{i}=i,Y_{i}=i+1$	$5$
$4$	$C_{i}=1$	$30$
$5$	$N,M \leq 1000$	$10$
$6$	无附加限制	$40$