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:
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^{4}, 1 ≤ m ≤ 10^{4}, that the nodes are numbered from 0, and that all costs are integers between 1 and 10^{9}.
Output
Print the answer to each query of the second type, and a blank line after every case.
Hint
Beware of overflows.
Input
12 10 0 1 4 0 4 1 1 2 7 1 5 2 1 7 3 2 3 5 2 6 2 6 11 3 7 8 2 7 9 1 7 10 4 q 2 4 q 1 7 q 0 4 q 3 3 q 8 1 q 4 2 c 1 7 10 c 6 11 1 q 11 0 q 8 4 4 5 0 1 1 1 2 1 2 3 1 q 0 1 q 0 2 q 0 3 c 1 2 10 q 0 3
Output
12 3 1 0 5 12 14 17 1 2 3 12