HLD

루트가 $1$번 정점인 트리가 $N$개의 정점으로 주어진다. 각 간선은 heavy edge 또는 light edge 중 하나이다. 각 정점에서 자식으로 향하는 간선 중에서는 heavy edge가 최대 하나만 될 수 있다. 트리의 heavy-light decomposition은 이 조건을 만족해야 한다.

처음에는 비어 있는 단순 경로의 다중집합 $T$가 있다. 위 조건을 지키면서, $T$에 맞게 각 간선에 heavy 또는 light를 배정한다. $T$가 갱신될 때마다 $T$에 있는 모든 경로가 포함하는 light edge의 총개수가 최소가 되는 배정을 구하라.

총 $Q$번의 갱신이 주어진다. 각 질의는 세 정수 $s$, $e$, $k$로 이루어지며, 정점 $s$에서 $e$까지의 단순 경로 $k$개를 $T$에 추가한다. 매 갱신 후 $T$의 모든 경로에 대한 light edge 총개수의 최솟값을 출력하라.

첫 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다.

이어지는 $N-1$개의 줄 중 $i$번째 줄에는 $i$번째 간선이 정점 $x_i$와 $y_i$를 잇는다는 뜻의 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다.

이어지는 $Q$개의 줄 중 $i$번째 줄에는 $i$번째 갱신을 나타내는 세 정수 $s$, $e$, $k$가 공백으로 구분되어 주어진다. 갱신은 입력 순서대로 처리되며, 각 갱신의 효과는 누적된다.

각 갱신 후의 답을 한 줄에 하나씩, 총 $Q$줄에 출력한다.

• $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)$
• 주어진 간선들은 트리를 이룬다.
• $1 \le s, e \le N$, $s \neq e$
• $1 \le k \le 10^9$
• 입력의 모든 값은 정수이다.