← 返回题目列表

Codeforces · 396/C

C. 关于改变树

中文机器翻译题面 查看原题

给你一棵有根树,由编号为 1 到 n 的 n 个顶点组成。树的根是顶点编号 1。

最初所有顶点都包含数字 0。然后是 q 个查询,每个查询都有以下两种类型之一:

- 查询的格式:1 v x k。响应查询,需要在顶点 v 处的数字上添加 x;对距离 1 处的顶点 v 的后代处的数字添加 x - k;依此类推,对于写在距离 i 处的顶点 v 的后代中的数字,您需要添加 x - (i·k)。两个顶点之间的距离是这些顶点之间的最短路径中的边数。
- 查询的格式:2 v。在回复查询时,您应该打印以顶点 v 模 1000000007 (109 + 7) 编写的数字。

处理输入中给出的查询。

输入

第一行包含整数 n (1 ≤ n ≤ 3·105) — 树中的顶点数。第二行包含 n - 1 个整数 p2, p3, ... pn (1 ≤ pi < i),其中 pi 是树中顶点 i 的父顶点的编号。

第三行包含整数 q (1 ≤ q ≤ 3·105) — 查询数。接下来的 q 行包含查询,每行一个。该行中的第一个数字是类型。它代表查询的类型。如果 type = 1,则接下来跟随空格分隔的整数 v、x、k (1 ≤ v ≤ n;0 ≤ x < 109 + 7;0 ≤ k < 109 + 7)。如果 type = 2,则 next 紧随整数 v (1 ≤ v ≤ n) — 您需要在其中查找数字值的顶点。

输出

对于第二类型的每个查询,在单行上打印查询中写入顶点的数字。打印以 1000000007 为模的数字 (109 + 7)。

示例

输入 #1

3
1 1
3
1 1 2 1
2 1
2 2

输出 #1

2
1

注意

您可以在这里阅读有关有根树的信息:http://en.wikipedia.org/wiki/Tree_(graph_theory)。