시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB35262270.968%

문제

In the Republic of JOI, there are N cities numbered from 1 to N. The cities are connected with N − 1 roads. People in the Republic of JOI are travelling between cities using these roads. They can pass each of the roads in both directions. They can travel between any two cities by passing through one or several roads.

Mr. IOI is a candidate for the president of the Republic of JOI. Of course, to become the president, he must perform the campaign for the presidential election. His secretary made M plans for the election campaign. In the i-th plan, Mr. IOI will travel from the city Ai to the city Bi passing through minimum number of roads, and make a public speech in each of the cities on the way (including the city Ai and the city Bi). Because his secretary is brilliant, it is known that Mr. IOI will get Ci votes if the i-th plan is performed. It is possible to perform several plans.

However, people in the Republic of JOI are impatient. If Mr. IOI makes public speeches more than once in the same city, he will lose the support from people in the Republic of JOI.

Because Mr. IOI would like to become the president, he wants to get as many votes as possible. Since you are a superprogrammer in the Republic of JOI, he asked you to write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election under the assumption that he will not make public speeches more than once in the same city.

Given the number N of cities in the Republic of JOI, the information on the roads, the number M of plans for the election campaign, and information of each plan, write a program which calculates the maximum number of votes Mr. IOI can get in the presidential election.

입력

Read the following data from the standard input.

  • The first line of input contains an integer N, the number of cities in the Republic of JOI.
  • The i-th line (1 ≤ i ≤ N − 1) of the following N − 1 lines contains two space separated integers Xi, Yi. This means the i-th road connects the city Xi and the city Yi.
  • The folloing one line contains an integer M, the number of plans for the election campaign.
  • The i-th line (1 ≤ i ≤ M) of the following M lines contains three space separated integers Ai, Bi, Ci. This means, in the i-th plan, Mr. IOI will travel from the city Ai to the city Bi passing through minimum number of roads, and he will get Ci votes if this plan is performed.

출력

The output should consist of one line, and contain one integer which denotes the maximum number of votes Mr. IOI can get in the presidential election.

제한

All input data satisfy the following conditions.

  • 2 ≤ N ≤ 100 000.
  • 1 ≤ Xi ≤ N.
  • 1 ≤ Yi ≤ N.
  • Xi ≠ Yi (1 ≤ i ≤ N − 1).
  • People can travel between any two cities by passing through one or several roads.
  • 1 ≤ M ≤ 100 000.
  • 1 ≤ Ai ≤ N.
  • 1 ≤ Bi ≤ N.
  • Ai, Bi (1 ≤ i ≤ M).
  • 1 ≤ Ci ≤ 10 000.

서브태스크 1 (10점)

  • M ≤ 15

서브태스크 2 (5점)

  • Xi = i (1 ≤ i ≤ N-1)
  • Yi = i+1 (1 ≤ i ≤ N-1)
  • Ci = 1 (1 ≤ i ≤ M)

서브태스크 3 (5점)

  • Xi = i (1 ≤ i ≤ N-1)
  • Yi = i+1 (1 ≤ i ≤ N-1)

서브태스크 4 (30점)

  • Ci = 1 (1 ≤ i ≤ M)

서브태스크 5 (10점)

  • N ≤ 1 000
  • M ≤ 1 000

서브태스크 6 (40점)

There are no additional constraints.

예제 입력 1

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

예제 출력 1

19

In this sample input, the optimal strategy is to perform the plan 1 and the plan 3 for the election campaign.

예제 입력 2

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

예제 출력 2

18

This sample input satisfies the constraints of the subtask 3.

예제 입력 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

3

This sample input satisfies the constraints of the subtask 4.

예제 입력 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

예제 출력 4

29191

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.