树上询问

题目描述:

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

给出三种操作：

1. Add(x,d)操作：将 x 到根的路径上所有点的 ki←ki+d
2. Mul(x,d)操作：将 x 到根的路径上所有点的 ti←ti+d×ki
3. Query(x) 操作：询问点 x 的权值 tx

输入格式:

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

输出格式:

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

样例输入:

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

样例输出:

45

提示:

1≤n,m≤100000,−10≤d≤10。

时间限制: 500ms
空间限制: 512MB

---