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}<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) $ .
输入输出样例
输入样例 #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).