Tree Circuit Voltage

You are given a tree‐structured electrical network with n nodes. Each undirected edge represents a branch that contains a resistor of \(10000\,\Omega\) and an additional resistor of \(10000\,\Omega\) connected from the branch (mid‐point) to ground. Furthermore, all leaf nodes (nodes whose degree is 1) are directly connected to ground (their voltage is fixed to 0).

The network supports two types of operations:

• C u v w: On the edge connecting nodes u and v (it is guaranteed that there is an edge between u and v), a battery of w volts is inserted in series. The battery is placed on the u side so that its negative terminal faces node u. (Multiple batteries may be inserted on the same edge; their effects add up.)
• Q u: Query the current voltage at node u relative to ground.

Due to the resistor network (each branch also has a resistor to ground) the effect of a battery inserted on an edge shows up as a fixed voltage difference between the two endpoints of that edge. In fact, if we fix a root for the tree at the smallest-indexed leaf (which is at 0 volts because it is connected to ground), then the insertion of a battery on an edge will enforce a relative voltage jump along the direction defined by the tree. More precisely, suppose that after rooting the tree, the edge between nodes u and v is oriented so that one is the parent and the other is the child. Then an operation C u v w (where an edge exists between u and v) is handled as follows:

• If u is the parent of v, then the battery forces the constraint V(v) = V(u) + w.
• If u is the child of v, then the battery forces V(u) = V(v) - w.

The final voltage at any node is determined by the cumulative effect of all batteries along the unique path from the root (grounded leaf) to that node. In other words, if we define an edge weight for each edge (from parent to child) that is initially 0 and add w (or subtract w) when a battery is inserted as described above, then the voltage at a node u is the sum of these edge‐weights along the path from the root to u.

It is guaranteed that the input operations are consistent with the physical model and that all queries can be answered by computing this cumulative sum.

Input Format:

The first line contains two integers n and m — the number of nodes in the tree and the number of operations, respectively.

The next n − 1 lines each contain two integers u and v, indicating that there is an edge between nodes u and v.

Then m lines follow. Each line is in one of the following two formats:

• C u v w: insert a battery on the edge between u and v (with the battery placed on the u side) of voltage w volts.
• Q u: query the voltage at node u (relative to ground).

Output Format:

For each query operation, output a single integer — the voltage at the specified node.

Note: To solve the problem efficiently, it is recommended to root the tree at the smallest-indexed leaf (which is at 0 volts) and precompute the Euler Tour of the tree. A Binary Indexed Tree (Fenwick Tree) or segment tree can then be used to support range updates (when a battery is added, its effect applies to the entire subtree of the (child) node) and point queries (the voltage at a node is the cumulative sum along the path from the root).

inputFormat

The input begins with two integers n and m separated by a space, where n is the number of nodes and m is the number of operations.

Then follow n − 1 lines, each containing two integers u and v (1 ≤ u, v ≤ n) that denote an edge of the tree.

Then there are m lines, each being either in the format C u v w or Q u (1 ≤ u, v ≤ n, and w is an integer representing the battery voltage).

outputFormat

For every query operation, output one line with a single integer — the voltage at the queried node.

sample

4 3
2 1
2 3
2 4
C 2 4 5
Q 2
Q 4

0
5

</p>