1217 : ytree
Time Limit: 2 Sec Memory Limit: 512 Mb Submitted: 15 Solved: 7Description
小Y很羡慕设计出自己数据结构的人,于是小Y也尝试设计一种新的树型结构想要支持以下操作:
- \(1\) \(v\) \(x\) \(k\),设 \(u\) 是以 \(v\) 号点为根的子树中的一个点(\(u\) 可以等于\(v\)),若 \(u\) 与 \(v\) 的深度差为 \(d\),则给 \(u\) 号点加上 \((x+k*d)*(-1)^{d}\)
- \(2\) \(v\),询问\(v\) 号点的权值 \(mod (1e9+7)\)之后的值, (规定1 号节点为根)
- \(3\) \(v\),将之前操作在以\(v\)为根的子树(包括\(v\))的操作\(1\)都撤销
Input
第一行包含两个正整数 \(N\) 和\(M\),\(N\) 为树上的点数,\(M\) 操作的数量。
第\(2\)~\(N\) 行,每行一个正整数,第\(i\)行的正整数是\(i\)号节点的父亲。
再接下来 \(M\) 行,格式为”\(1\) \(v\) \(x\) \(k\)“,”\(2\) \(v\)“或”\(3\) \(v\)“,含义如题。
对于 \(100\%\) 的数据, \(1 \leq n \leq 2*10^5\), \(1 \leq m \leq 10^5\), \(1 \leq |x|, |k| \leq 10^3\)。
Output
对于每个\(2\) 操作输出一行,为 \(v\)号点的权值\(mod (1e9+7)\)之后的值,负数取模要化为正数 (详见样例 )
Sample
5 11 1 1 3 3 1 1 0 2 2 1 2 2 3 3 2 4 3 1 1 3 1 3 2 3 2 4 3 1 2 1
0 1000000005 4 1 1000000003 0