HLD

You are given a rooted tree consisting of $N$ vertices. Its root is vertex $1$. Let's consider about a heavy-light decomposition of a tree, where each edge is either a heavy edge or a light edge. For each vertex, among all edges connecting the vertex with its children, at most one edge can be a heavy edge.

In this problem, we have a multiset of simple paths $T$, which is initially empty. We will assign each edge to be a heavy edge or a light edge according to $T$, satisfying the condition above.

Each time a update is done on $T$, your task is to find an assignment of edges that minimizes the sum of the number of light edges of all paths in $T$.

$Q$ updates are given in total. Each query consists of three integers $s$, $e$, and $k$, meaning $k$ copies of the simple path from $s$ to $e$ are inserted into $T$. Find the minimum sum of the number of light edges of all paths in $T$ after each update.

The first line contains two space-separated integers $N, Q$.

The $i$-th of the following $N-1$ lines contains two space-separated integers $x_i$ and $y_i$, meaning that the $i$-th edge connects vertices $x_i$ and $y_i$ in the tree.

The $i$-th of the following $Q$ lines contains three space-separated integers $s$, $e$, and $k$, describing each update.

The update are processed in the input order, and result of each update is accumulated.

Print the answer after each update in $Q$ lines.

• $2 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le x_i, y_i \le N$, $x_i \neq y_i$ $(1 \le i \le N-1)$
• It is guaranteed that the given edges form a tree.
• $1 \le s, e \le N$, $s \neq e$
• $1 \leq k \leq 10^9$
• All values in the input are integers.