Samcompu’s Water Plan

Samcompu is planning a "water" (procrastination) session. His goal is to surf websites during the intervals when the teacher is away from the computer lab. The teacher will leave the lab T times. In the j-th departure, the teacher is absent for \( tim_j \) seconds.

Samcompu has a secret technique that allows him to switch between his N water websites almost instantaneously; he can save the webpage information in seconds. Hence, the switching time is negligible. Note that there are exactly \( N-1 \) available transitions (ensuring connectivity among all \( N \) websites). For the \( i\)-th transition, moving from website \( u_i \) to \( v_i \) incurs a danger level of \( w_i \). If during a water session any transition on the path has a danger level \( w_i \) such that \( tim_j \leq w_i \), then Samcompu won’t be able to handle the potential system freeze and will be caught by the teacher.

Furthermore, during the teacher's j-th departure, one specific transition \( K_j \) becomes unavailable. Note that after each water session, the unavailable transition is restored. Each water session can start at any website and end at any website. Two water plans are considered different if and only if their starting website or ending website differs.

A water plan is safe if and only if, when the teacher is away for \( tim_j \) seconds, the unique path (in the available network) between the starting and ending websites does not contain any transition with \( w_i \) such that \( tim_j \leq w_i \). In other words, every transition used must satisfy \( w_i < tim_j \).

Input/Output Specifications: In each test event, you are given a tree of \( N \) websites (with \( N-1 \) transitions) and the teacher leaves the lab \( T \) times. For each event, after disabling the specified transition \( K_j \), count the total number of safe water plans. A safe water plan is defined as an ordered pair (start, end) of websites (they may be the same), such that in the graph obtained by removing the disabled transition and further ignoring all transitions with danger levels \( \geq tim_j \), the start and end websites are connected. The answer for each event is the sum, over every connected subcomponent in the safe graph, of \( (\text{size of subcomponent})^2 \).

Input Format:

N T
u1 v1 w1
nu2 v2 w2
... (N-1 lines in total)
tim_1 K_1
tim_2 K_2
... (T lines in total)

</p>

Output Format:

ans_1
ans_2
...
ans_T

where ansj is the total number of safe water plans for the j-th teacher departure event.

Note: The graph initially forms a tree. For each event, after removing the disabled transition, the tree becomes a forest. Within each connected component of this forest, remove all transitions with danger level \( \geq tim_j \) to obtain the safe subgraph. Then, if a connected safe subgraph has \( s \) vertices, it contributes \( s^2 \) to the answer (since plans are counted as ordered pairs, including trivial plans with the same start and end website).

inputFormat

The first line contains two integers \( N \) and \( T \), representing the number of websites and the number of times the teacher leaves, respectively.

The following \( N-1 \) lines each contain three integers \( u \), \( v \), and \( w \), where there is a transition between website \( u \) and website \( v \) with danger level \( w \). The transitions are numbered from 1 to \( N-1 \) in the order given.

The next \( T \) lines each contain two integers: \( tim_j \) and \( K_j \). For the \( j \)-th event, \( tim_j \) is the time (in seconds) the teacher is absent, and \( K_j \) is the index of the transition that is temporarily disabled.

N T
u1 v1 w1
nu2 v2 w2
... (N-1 lines)
tim_1 K_1
tim_2 K_2
... (T lines)

</p>

outputFormat

Output \( T \) lines. The \( j \)-th line should contain a single integer representing the total number of safe water plans for the teacher's \( j \)-th departure.

sample

3 2
1 2 3
2 3 2
3 1
2 2

5
3

</p>