HLD

You are given a rooted tree with $N$ vertices. The root is vertex $1$. Each edge is either a heavy edge or a light edge. For each vertex, at most one of the edges to its children can be a heavy edge. This is the condition that a heavy-light decomposition of the tree must satisfy.

There is a multiset of simple paths $T$, which is initially empty. Assign each edge a heavy or light label according to $T$, while satisfying the condition above. After each update to $T$, find an assignment that minimizes the total number of light edges over all paths in $T$.

$Q$ updates are given in total. Each query consists of three integers $s$, $e$, and $k$, which insert $k$ copies of the simple path from $s$ to $e$ into $T$. After each update, print the minimum total number of light edges over all paths in $T$.

The first line contains two space-separated integers $N$ and $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$.

The $i$-th of the following $Q$ lines contains three space-separated integers $s$, $e$, and $k$, describing the $i$-th update. Updates are processed in input order, and the effect of each update accumulates.

Print the answer after each update on its own line, for $Q$ lines in total.

• $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)$
• The given edges form a tree.
• $1 \le s, e \le N$, $s \neq e$
• $1 \le k \le 10^9$
• All values in the input are integers.