apa

Se dă un arbore cu $N$ noduri, în fiecare nod având un vas comunicant cu capacitate infinită.
Să se răspundă la $Q$ întrebări de forma $(u, v, h)$, cu următoarea semnificație: vom considera lanțul de la $u$ la $v$ și vom turna $h$ litri de apă în nodul $u$. Prin acest proces valorile de pe lanțul de la $u$ la $v$ vor fi (începând cu $u$) $h, h-1, \ldots, 1, 0, 0, \ldots, 0$. Valoarea dintr-un nod care nu se află pe lanțul de la $u$ la $v$ este valoarea care se află în cel mai apropiat nod care se află pe lanțul de la $u$ la $v$. Pentru fiecare query, se cere suma valorilor din arbore.

Cerință

Să se răspundă la cele $Q$ întrebări.

Date de intrare

Pe prima linie se află numerele $N$ și $Q$. Următoarele $N-1$ conțin fiecare câte o pereche de numere $(u, v)$ cu semnificația că există o muchie între nodurile $u$ și $v$. Următoarele $Q$ linii conțin fiecare câte trei numere, $(u, v, h)$, reprezentând elementele unui query.

Date de ieșire

Fișierul de ieșire va conține $Q$ linii, a $i$-a linie reprezentând răspunsul pentru al $i$-lea query.

Restricții și precizări

• $1 \leq N, Q \leq 200 000$
• $1 \leq u, v \leq N$
• $1 \leq h \leq 10^9$
• Pentru $8$ puncte: $1 \leq N, Q \leq 1000$
• Pentru $6$ puncte: Toate query-urile au același $u$
• Pentru $12$ puncte: Toate query-urile au același $v$
• Pentru $53$ de puncte: $1 \leq N \leq 50000$
• Pentru $21$ de puncte: Fără alte restricții

Exemple

Intrare

10 3
1 2
2 3
3 4
3 5
3 6
4 7
4 8
6 9
6 10
7 10 5
7 10 3
1 10 8

Ieșire

30
11
59

Explicații

Pentru primul query, nodul $7$ este singurul cu $5$ litri de apă, nodurile $4$ și $8$ conțin $4$ litri de apă, nodurile $5, 3, 2$ și $1$ conțin $3$ litri de apă, nodurile $6$ și $9$ conțin $2$ litri de apă, iar nodul $10$ conține un litru de apă.