Heavy-light decomposition P53018

Let T be a rooted tree with n nodes. For every node u, let S(u) denote the size (the number of nodes) of the subtree rooted at u, including u itself. Let p_u denote the parent of u.

An edge {u, p_u} is called heavy if 2S(u) > S(p_u), and light otherwise. Note that at most one child of every node can be connected by a heavy edge. It is easy to see that the number of light edges in the path from any node to the root of T is at most O(logn). Moreover, the connected components of the subgraph that only uses the heavy edges are just paths and single nodes.

Now consider the classic Lowest Common Ancestor Problem (given two nodes, find the closest node to them that is an ancestor of both). The following simple code returns the LCA of two given nodes in cost O(logn).

int lca(int u, int v) {
  while (head[u] != head[v]) {
    if (depth[head[u]] > depth[head[v]]) u = parent[head[u]];
    else v = parent[head[v]];
  }
  return depth[u] < depth[v] ? u : v;
}

where depth and parent mean exactly what their names suggest and head[u] is the node closest to the root that belongs to the same heavy path as u (maybe u itself).

With all the information above, perhaps you are ready to solve the following problem. Given an unrooted tree with costs at the edges, perform two types of queries:

• c u v x: Change to x the cost of the edge {u, v}.
• q u v: Print the sum of the costs in the path from u to v.

Input

Input consists of several cases. Every case begins with n and the number of queries m. Follow n − 1 triples u v x, meaning that u and v are connected by an edge of cost x. Follow m queries. Assume 2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10⁴, that the nodes are numbered from 0, and that all costs are integers between 1 and 10⁹.

Output

Print the answer to each query of the second type, and a blank line after every case.

Hint

Beware of overflows.