给你一棵由 $$$n$$$ 个顶点组成的树。最初,每个顶点都有一个值$$$0$$$。
您需要执行两种类型的 $$$m$$$ 查询:
1. 给定一个顶点索引 $$$v$$$。打印顶点 $$$v$$$ 的值。
2. 给定两个顶点索引 $$$u$$$ 和 $$$v$$$ 以及值 $$$k$$$ 和 $$$d$$$ ($$$d \le 20$$$)。您需要将 $$$k$$$ 添加到每个顶点的值,使得从该顶点到从 $$$u$$$ 到 $$$v$$$ 的路径的距离小于或等于 $$$d$$$。
两个顶点 $$$x$$$ 和 $$$y$$$ 之间的距离等于从 $$$x$$$ 到 $$$y$$$ 的路径上的边数。例如,从 $$$x$$$ 到 $$$x$$$ 本身的距离等于 $$$0$$$。
从顶点 $$$v$$$ 到从 $$$x$$$ 到 $$$y$$$ 的某个路径的距离等于从 $$$v$$$ 到从 $$$x$$$ 到 $$$y$$$ 的路径上的任意顶点的距离中的最小值。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行包含树的边缘 - 每行一个。每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$) 代表树的一条边。保证给定的边形成一棵树。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 查询数。
接下来的 $$$m$$$ 行包含查询 - 每行一个。每个查询都有以下两种类型之一:
- $$$1$$$ $$$v$$$ ($$$1 \le v \le n$$$) — 第一种类型的查询;
- $$$2$$$ $$$u$$$ $$$v$$$ $$$k$$$ $$$d$$$ ($$$1 \le u, v \le n$$$; $$$1 \le k \le 1000$$$; $$$0 \le d \le 20$$$) — 第二种类型的查询。
对输入的附加约束:至少有一个第一类型的查询。
输出
对于第一种类型的每个查询,打印相应顶点的值。
示例
输入 #1
6 1 2 1 3 4 2 5 2 3 6 14 2 4 5 10 2 1 3 1 6 2 1 1 10 20 2 6 6 10 20 1 3 2 3 2 10 0 2 5 2 10 1 1 1 1 2 1 3 1 4 1 5 1 6
输出 #1
10 0 30 50 50 40 40 40 20
注意
第一个示例中的树:
- "$$$2$$$ $$$4$$$ $$$5$$$ $$$10$$$ $$$2$$$":受影响的顶点为$$$\{4, 2, 5, 1, 3\}$$$;
- "$$$2$$$ $$$1$$$ $$$1$$$ $$$10$$$ $$$20$$$" 和 "$$$2$$$ $$$6$$$ $$$6$$$ $$$10$$$ $$$20$$$":所有顶点都会受到影响,因为距离 $$$1$$$对于任何顶点,($$$6$$$) 都小于 $$$20$$$;
- "$$$2$$$ $$$3$$$ $$$2$$$ $$$10$$$ $$$0$$$":受影响的顶点为 $$$\{3, 1, 2\}$$$;
- "$$$2$$$ $$$5$$$ $$$2$$$ $$$10$$$ $$$1$$$":受影响的顶点为 $$$\{5, 2, 4, 1\}$$$。