You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

SHOI2012 D2T3

题目描述

Harry Potter 新学了一种魔法：可以改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有 $N$ 个节点，其中节点 $0$ 是根节点，每个节点 $u$ 的父亲记为 $fa[u]$，保证有 $fa[u] < u$ 。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即 $0$ 个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：A u v d 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：Q u。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？

输入格式

第一行一个正整数 $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$ 本身的。

输出格式

对于所有的 Q 操作，依次输出询问的答案，每行一个。答案可能会超过 $2^{32}$ ，但不会超过 $10^{15}$ 。

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

3
3
2