[AdditionalFile6208.zip](file://AdditionalFile6208.zip?type=additional_file)

#6208. 树上询问

标签: 传统 | 时间限制: 500 ms | 内存限制: 512 MiB |

题目描述

有一棵 $n$ 节点的树，根为 $1$ 号节点。每个节点有两个权值 $k_i, t_i$，初始值均为 $0$。

给出三种操作：

1. $\mathrm{Add}( x , d )$ 操作：将 $x$ 到根的路径上所有点的 $k_i\leftarrow k_i + d$
2. $\mathrm{Mul}( x , d )$ 操作：将 $x$ 到根的路径上所有点的 $t_i\leftarrow t_i + d \times k_i$
3. $\mathrm{Query}( x )$ 操作：询问点 $x$ 的权值 $t_x$

输入格式

第一行一个整数 $n$。
之后的 $n-1$ 行，每行两个整数 $u, v$，表示 $u$ 与 $v$ 间有一条无向边。
第 $n+1$ 行一个整数 $m$ 表示操作个数。
之后的 $m$ 行，第一个数表示操作类型 $\mathrm{opt}$；
若 $\mathrm{opt}$ 为 $1$ 或 $2$，则接下来有两个数 $x, d$；
若 $\mathrm{opt}$ 为 $3$，则只有一个数 $x$。

输出格式

对于每一个询问，输出一行表示询问点的 $t_i$ 值。

样例

输入

3
1 2
1 3
5
1 1 2
1 2 1
2 3 10
2 2 5
3 1

输出

45

数据范围与提示

$1 \leq n, m \leq 100000, -10 \leq d \leq 10$。
已经按照 LOJ 的运行速度调整时限。