30296번 - 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.

힌트