#6208. 树上询问

内存限制:512 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一棵 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 值。

样例

样例输入 1

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

样例输出 1

45

数据范围与提示

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