Description

Harry Potter has learned a new kind of magic: he can change the number of fruits on a tree. Overjoyed, he found a huge fruit tree to test his new spell.

This fruit tree has $N$ nodes. Node $0$ is the root, and the parent of each node $u$ is denoted by $fa[u]$, with the guarantee that $fa[u] < u$. Initially, all the fruits on this tree were removed by Dumbledore’s magic, so every node on this fruit tree has no fruits (that is, $0$ fruits).

Unfortunately, Harry’s magic is not yet perfect; he can only uniformly increase the number of fruits on all nodes along a path in the tree by a fixed amount. In other words, Harry’s magic can be described as: A u v d. This means adding $d$ to the number of fruits on every node on the path between nodes $u$ and $v$.

Next, to help check whether Harry’s magic is working, you need to tell him some information about the fruit tree during the process: Q u. This asks for the total number of fruits currently in the subtree rooted at node $u$.

Input Format

The first line contains a positive integer $N$ $(1 \leq N \leq 100000)$, the total number of nodes in the fruit tree. Nodes are labeled $0, 1, \dots, N - 1$, and $0$ is the root.

The next $N - 1$ lines each contain two integers $a, b$ $(0 \leq a < b < N)$, indicating that $a$ is the parent of $b$.

Then follows a positive integer $Q$ $(1 \leq Q \leq 100000)$, the number of operations.

Then there are $Q$ lines, each being one of the following two types:

1. A u v d: Add $d$ to the number of fruits on every node along the path from $u$ to $v$. It is guaranteed that $0 \leq u, v < N$, $0 < d < 100000$.
2. Q u: Query the total number of fruits in the subtree rooted at $u$, including $u$ itself.

Output Format

For every Q operation, output the answer in order, one per line. The answer may exceed $2^{32}$, but will not exceed $10^{15}$.

4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2

3
3
2

Hint

Translated by ChatGPT 5