8195: [SHOI2012]魔法树
[Creator : ]
Description
# 题目背景
SHOI2012 D2T3
# 题目描述
Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。
这棵果树共有 $N$ 个节点，其中节点 $0$ 是根节点，每个节点 $u$ 的父亲记为 $fa$，保证有 $fa < u$ 。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即 $0$ 个果子）。
不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：`A u v d` 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。
接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：`Q u`。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？
SHOI2012 D2T3
# 题目描述
Harry Potter 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。
这棵果树共有 $N$ 个节点，其中节点 $0$ 是根节点，每个节点 $u$ 的父亲记为 $fa$，保证有 $fa < u$ 。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即 $0$ 个果子）。
不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：`A u v d` 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。
接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：`Q u`。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？
Input
第一行一个正整数 $N (1 \leq N \leq 100000)$，表示果树的节点总数，节点以 $0,1,\dots,N - 1$ 标号，$0$ 一定代表根节点。
接下来 $N - 1$ 行，每行两个整数 $a,b (0 \leq a < b < N)$，表示 $a$ 是 $b$ 的父亲。
接下来是一个正整数 $Q(1 \leq Q \leq 100000)$，表示共有 $Q$ 次操作。
后面跟着 $Q$ 行，每行是以下两种中的一种：
1. `A u v d`，表示将 $u$ 到 $v$ 的路径上的所有节点的果子数加上 $d$。保证 $0 \leq u,v < N,0 < d < 100000$
2. `Q u`，表示询问以 $u$ 为根的子树中的总果子数，注意是包括 $u$ 本身的。
接下来 $N - 1$ 行，每行两个整数 $a,b (0 \leq a < b < N)$，表示 $a$ 是 $b$ 的父亲。
接下来是一个正整数 $Q(1 \leq Q \leq 100000)$，表示共有 $Q$ 次操作。
后面跟着 $Q$ 行，每行是以下两种中的一种：
1. `A u v d`，表示将 $u$ 到 $v$ 的路径上的所有节点的果子数加上 $d$。保证 $0 \leq u,v < N,0 < d < 100000$
2. `Q u`，表示询问以 $u$ 为根的子树中的总果子数，注意是包括 $u$ 本身的。
Output
对于所有的 `Q` 操作，依次输出询问的答案，每行一个。答案可能会超过 $2^{32}$ ，但不会超过 $10^{15}$ 。
Sample 1 Input
4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2
Sample 1 Output
3
3
2