Binary Tree Operations

You are given a rooted tree with N nodes numbered from 1 to N. Node 1 is the root. Each node has an initial weight. The tree is provided as a list of edges in a parent-child relationship. You are also given M commands to process on this tree.

There are two types of commands:

• A X D: Add an integer D to the weight of every node in the subtree rooted at node X.
• S X Y: Query the maximum weight among all nodes on the unique simple path from node X to node Y (inclusive). The path is defined as the concatenation of the path from X to the lowest common ancestor (LCA) of X and Y, and from the LCA to Y (note that the LCA is counted only once).

Note: If the tree has only one node, there will be no edge input.

The operations may affect later queries, so it is necessary to update the tree weights for subsequent operations accordingly.

The formulas used in this problem may be expressed in LaTeX. For example, the number of nodes is given by \( N \), and the weight update for a node \( i \) during a subtree addition can be written as:

[ w_i \leftarrow w_i + D \quad \text{for all } i \text{ in the subtree of } X. ]

Your task is to handle all the commands and for every query command output the corresponding result.

inputFormat

The input is read from standard input (stdin) with the following format:

N M
u1 v1
u2 v2
... (N-1 lines, each representing an edge from parent to child; if N=1 then this section is skipped)
w1 w2 ... wN
command1
command2
... 
commandM

Here:

• N is the number of nodes.
• M is the number of commands.
• Each of the next N-1 lines contains two integers u v indicating there is an edge from u (parent) to v (child).
• The next line contains N integers representing the initial weights of nodes 1 through N.
• Then follow M lines, each being a command in the form described above.

outputFormat

For each command of type S, output the resulting maximum weight on the corresponding path, each on a new line.

## sample

5 5
1 2
1 3
2 4
2 5
1 2 3 4 5
S 1 5
A 2 10
S 2 4
S 1 4
S 1 3

5
14
14
3

</p>