1217 : ytree
- 时间限制Time Limit
- 2 秒Sec
- 内存限制Memory Limit
- 512 兆MB
- 提交次数Submitted
- 71 次Times
- 通过次数Solved
- 23 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
小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
来源Source
湖南省第十九届大学生计算机程序设计竞赛(HNCPC2023)
题目到此结束End of problem