P3833 [SHOI2012] Magic Tree

SHOI2012 D2T3.

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$.

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.

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

Translated by ChatGPT 5