A9463. On Changing Tree

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·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.

The first line contains integer $n$ ( $1<=n<=3·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·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.

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$ $(10^{9}+7)$ .

You can read about a rooted tree here: http://en.wikipedia.org/wiki/Tree\_(graph\_theory).