On Changing Tree

题意翻译

你在纸上画了一棵有n个点的有根树，树的根编号为1. 一开始每个节点上面的值都为0。 现在有q个询问，每个询问有两种类型： 1 v x k 你需要给v节点的值增加 x，如果v的子孙u，与v的距离为i，那么需要给节点u上的值增加 (x - i * k)。两个点间的距离定义为两点之间的最短路。 2 v 输出节点v上的值。 对于每个询问，你需要输出 mod 1000000007后的值。

题目描述

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}&lt;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&lt;10^{9}+7 $ ; $ 0<=k&lt;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) $ .

输入输出样例

输入样例 #1

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

输出样例 #1

2
1

说明

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