Layered Urban Tree Queries

You are given a tree with n nodes (numbered from 1 to n) and m operations. The tree is rooted at node 1 and each node x has an associated weight v_x (initially all weights are 0).

For two nodes x and y in the tree, define the distance \(\text{dis}(x,y)\) to be the number of edges on the unique simple path between x and y.

For any node x, let \(\text{subtree}(x)\) denote the subtree of the tree rooted at x. For each node x, define \[ f(x)=\max_{d\ge0}\;\sum_{\substack{y\in\text{subtree}(x)\\\text{dis}(x,y)=d}}v_y. \] That is, for each nonnegative integer d, you compute the sum of the weights of nodes in \(\text{subtree}(x)\) that are exactly d edges away from x; then \(f(x)\) is the maximum among these sums.

Then you are given m operations. Each operation provides three integers \(x\), \(w\), and \(y\). For an operation, perform the following two steps in order:

1. Update: set \(v_x \gets v_x + w\).
2. Query: compute \(\sum_{i\in\text{subtree}(y)}f(i)\) and output the result.

Note: All formulas above are displayed in LaTeX format.

inputFormat

The input begins with a line containing two integers n and m indicating the number of nodes and the number of operations, respectively.

Then follow n − 1 lines. Each of these lines contains two integers \(u\) and \(v\) representing an undirected edge in the tree.

After that, there are m lines. Each of these lines contains three integers \(x,\; w,\; y\) denoting an operation: update \(v_x\) by adding \(w\) (i.e. \(v_x \gets v_x+w\)) and then output \(\sum_{i\in\text{subtree}(y)}f(i)\).

You may assume that the tree is rooted at node 1.

outputFormat

For each operation, output a single line containing one integer: the answer of the query after performing the update.

sample

5 3
1 2
1 3
3 4
3 5
2 5 1
3 2 3
1 3 3

10
2
2