P15831 [JOI Open 2015] Election Campaign

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 $A_i$ to the city $B_i$ passing through minimum number of roads, and make a public speech in each of the cities on the way (including the city $A_i$ and the city $B_i$). Because his secretary is brilliant, it is known that Mr. IOI will get $C_i$ 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. ### Task 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 \leq i \leq N-1$) of the following $N-1$ lines contains two space separated integers $X_i, Y_i$. This means the $i$-th road connects the city $X_i$ and the city $Y_i$. - The following one line contains an integer $M$, the number of plans for the election campaign. - The $i$-th line ($1 \leq i \leq M$) of the following $M$ lines contains three space separated integers $A_i, B_i, C_i$. This means, in the $i$-th plan, Mr. IOI will travel from the city $A_i$ to the city $B_i$ passing through minimum number of roads, and he will get $C_i$ 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.

### Sample 1 Explanation In this sample input, the optimal strategy is to perform the plan 1 and the plan 3 for the election campaign. ### Sample 2 Explanation This sample input satisfies the constraints of the subtask 3. ### Sample 3 Explanation This sample input satisfies the constraints of the subtask 4. ### Constraints All input data satisfy the following conditions. - $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$). - People can travel between any two cities by passing through one or several roads. - $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$. ### Subtask #### Subtask 1 [10 points] - $M \leq 15$. #### Subtask 2 [5 points] - $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$). #### Subtask 3 [5 points] - $X_i = i$ ($1 \leq i \leq N-1$). - $Y_i = i+1$ ($1 \leq i \leq N-1$). #### Subtask 4 [30 points] - $C_i = 1$ ($1 \leq i \leq M$). #### Subtask 5 [10 points] - $N \leq 1\,000$. - $M \leq 1\,000$. #### Subtask 6 [40 points] There are no additional constraints.