Path Sum Queries on a Tree

You are given an undirected tree with (n) nodes numbered from 1 to (n) where each node has an initial value of 0. The tree is defined by its (n-1) edges. You have to perform (q) operations, which are of two types:

1. Update Operation: "U x y" means add the value (y) to node (x).
2. Query Operation: "Q x y" means compute the sum of values of all the nodes on the simple path between node (x) and node (y). Specifically, if the path is (a_1, a_2, \ldots, a_k), then the answer is given by (\sum_{i=1}^{k} value(a_i)).

The tree structure allows you to compute the parent and depth of each node using a BFS (Breadth-First Search) starting from node 1. For each query, you need to climb up from both nodes until they meet (i.e. reach their Lowest Common Ancestor, LCA), summing up the contributions along the way.

The problem tests your ability to handle tree traversals, queries on paths, and dynamic updates efficiently.

Note: All operations must be processed in the order they are given, and you should use standard input (stdin) and standard output (stdout) for reading the input and printing the results.

inputFormat

The first line contains two integers (n) and (q): the number of nodes in the tree and the number of operations, respectively. The following (n-1) lines each contain two integers (u) and (v) indicating an undirected edge between nodes (u) and (v). The next (q) lines each represent an operation. Each operation is in one of the following formats:

• U x y — update node (x) by adding value (y). • Q x y — output the sum of values on the simple path from node (x) to node (y).

outputFormat

For each query operation (lines starting with 'Q'), output the computed sum on a separate line. No output is required for update operations.## sample

5 5
1 2
1 3
3 4
3 5
U 1 5
Q 2 3
U 4 2
Q 2 4
Q 4 5

5
7
2