/ ALGORITHM

# CodeForces Round #232 (Div. 1) E

## Description

• $1\ v\ x\ k$ : 给节点 $v$ 的值加上 $x$，给它的子节点（和 $v$ 的深度差为 $i$ ） 加上 $x - k\times i$

• $2\ v$ : 查询 $v$ 的值

You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$. The root of the tree is a vertex number $1$.

Initially all vertices contain number $0$. Then come $q$ queries, each query has one of the two types:

• The format of the query: $1\ v\ x\ k$ . In response to the query, you need to add to the number at vertex $v$ number $x$; to the numbers at the descendants of vertex $v$ at distance $1$, add $x - k$; and so on, to the numbers written in the descendants of vertex $v$ at distance $i$, you need to add $x - (i\times k)$. The distance between two vertices is the number of edges in the shortest path between these vertices.

• The format of the query: $2\ v$ . In reply to the query you should print the number written in vertex $v$ modulo $1000000007\ (10^9 + 7)$.

Process the queries given in the input.

## Input

The first line contains integer $n\ (1 ≤ n ≤ 3 \times 10^5)$ — the number of vertices in the tree. The second line contains $n - 1$ integers $p_2, p_3, … p_n\ (1 ≤ p_i < i)$, where $p_i$ is the number of the vertex that is the parent of vertex $i$ in the tree.

The third line contains integer $q\ (1 ≤ q ≤ 3\times 10^5)$ — the number of queries. Next $q$ lines contain the queries, one per line. The first number in the line is type. It represents the type of the query. If type = 1, then next follow space-separated integers $v, x, k\ (1 ≤ v ≤ n; 0 ≤ x < 10^9 + 7; 0 ≤ k < 10^9 + 7)$. If type = 2, then next follows integer $v\ (1 ≤ v ≤ n)$ — the vertex where you need to find the value of the number.

## Output

For each query of the second type print on a single line the number written in the vertex from the query. Print the number modulo $1000000007 (109 + 7)$.

## Sample Input

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


## Sample Output

2
1


## Solution

$\det = x - i \times k = x - ( dep[v] - dep[u]) \times k = x + dep[u] \times k - dep[v] \times k$ ，在该式中，$u$ 的整个子树增加的值 $x + dep[u] \times k$ 是固定的，整个子树减少的值 $dep[v] \times k$ 和每个节点有关，但是有一部分是固定的，所以我们可以维护两个树状数组，做区间修改和点查询。

## AC code

#### Darron

The professional publishing platform