[Ynoi2016]炸脖龙II

题目背景

瞬间… 真要说的话,比瞬间还要短暂。 羽咲往悬崖的方向飞去。 瘦小的羽咲,比想象中更轻易地飞侠了悬崖。 我急忙跑向悬崖边。 然而,飞奔而出之后,方向并不是那么容易改变。 我失去了平衡,就这么摔倒在地。 只能一直用目光追寻着羽咲的身影。 飞出悬崖的羽咲。 身体浮在半空中。 在下一瞬间,便听任自由落体定律…径直坠下陡峭的悬崖 ![](https://cdn.luogu.com.cn/upload/pic/21200.png) 细长的双眼…注视着我的眼睛。 这是幻觉吗…还是现实… 卓司的指尖捅破了头盖骨… 这根本不可能的吧…人的手劲如何能够捏破头盖骨… 这毫无疑问是幻觉…不可能存在于现实中… 这种事,习武的我是最清楚不过的… 这种根本不可能的事… 尽管如此… 我的意识仍朦胧起来… 已经无法与这个世界保持联系了… “我…收下皆守哥哥的身体了哦…” ![](https://cdn.luogu.com.cn/upload/pic/21201.png) 司空见惯的风景。 比之前看到的风景更让人眼熟。 我所熟悉的风景… ![](https://cdn.luogu.com.cn/upload/pic/21202.png) “我会把他带走的…所以你走吧…” “卓司…那个电波小子,就让我把他带走…” “所以你就前进吧…” “在无法登上的坡道的尽头” “你不能停滞不前,必须前去迎接小羽” “好啦,打起精神来…皆守” “在这里告别吧…” ![](https://cdn.luogu.com.cn/upload/pic/21203.png) 轻飘飘的感觉。 瞬间,感觉到了周围空气的急速变冷。 扬起的灰尘伴随月光的照耀,在空中废物。 告别了永不相交的平行,我和羽咲被吸进了… 垂直下落的世界。 月光映照出羽咲身体的轮廓。 地面没有影子。 宛如高空飞翔一般… 远方传来警笛声。 在苍穹之下反复回想。 我仰望无限的天空,笔直坠下。 一刻也不远看丢,在我上方的羽咲… 月在笑。 神在笑。 笑这滑稽的姿势。 笑这喜剧般的悲剧。 群星旋转。 如舞如蹈。 夜空上的神,正嘲弄着我们。 就想把空瓶子扔在地上的天真的孩子一样… 世界变得一片空虚。 ![](https://cdn.luogu.com.cn/upload/pic/21204.png) 望不到尽头的坡道… 遥远而模糊的坡道… 宛如…我们就漫步在这样的世界中一般… 就算在意坡道的前方也毫无用处。 我们就在这坡道上快乐地走着。 ![](https://cdn.luogu.com.cn/upload/pic/21205.png)

题目描述

您在打galgame,突然听说苏联解体了,于是您发现您永远看不到一个活着的苏联人了,很郁闷,于是开始写一道数据结构题: 这是一道模(du)拟(liu)题。 你需要维护一棵包含 $n$ 个结点有根有序树(也就是说每个点的孩子是有“从左到右”的顺序的),初始根为 $1$,支持以下几个操作: `A(x,y)`:对 $x$ 进行路径压缩,即将 $x$ 到根路径上除了根之外的点的父亲设为根,这些点在根的孩子中的顺序保持原先路径上从浅到深的顺序。 `B(x,y)`:将根的孩子 $x,y$($x$ 在 $y$ 左边)以及之间的点按顺序展开成一条路径,$x$ 仍与根相连,涉及到的点原先的孩子都移至路径右侧。 `C(x,y)`:将树的根设为 $x$,此时原先在根到 $x$ 路径左侧的点仍在左侧且先相对顺序不变,右侧同理,$x$ 的孩子在 $x$ 成为根后在 $x$ 到原先的根的路径的右侧。 `D(x,y)`:给 $x$ 到根的路径上每个点的点权同时加一个数,并在这之后求 $x$ 到根的路径上的点权和。 `E(x,y)`:保证 $x$ 和 $y$ 父亲相同且 $x$ 在 $y$ 左侧,对在 $x$ 的父亲的孩子中,$x$ 到 $y$ 之间(含 $x,y$)的每个点的点权加上 $x+y$,并在这之后求这些点的点权和。 `F(x,y)`:给 $x$ 添加一个孩子 $y$,在最右边,这个操作在其它所有操作之前进行,用于描述树的初始形态。

输入输出格式

输入格式


第一行两个整数 $n,q$,分别表示树的结点数和操作次数。 接下来 $q$ 行,每行表示一个操作。

输出格式


对每个 `D` 或 `E` 操作,输出一行,表示答案对 $2^{32}$ 取模的结果。

输入输出样例

输入样例 #1

20 30
F(1,2)
F(1,3)
F(1,7)
F(1,9)
F(9,5)
F(3,8)
F(3,20)
F(3,6)
F(8,15)
F(8,19)
F(20,14)
F(20,12)
F(6,13)
F(6,18)
F(13,4)
F(12,11)
F(12,17)
F(17,10)
F(17,16)
E(3,9)
E(8,6)
A(12,0)
D(4,6)
E(2,7)
B(3,12)
D(4,6)
C(8,0)
D(13,5)
D(1,7)
E(12,14)

输出样例 #1

36
42
56
89
95
105
90
61

说明

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078 $2\leq n\leq 10^5$,$n\leq q\leq 2\times 10^5$,$0\leq x,y \leq n$。 保证操作合法。 为了对称,所有操作都有两个参数 $x,y$,但实际上 `A`,`C` 操作中不需用到 $y$,数据保证此时 $y=0$。   前 $n-1$ 个操作一定是 `F` 操作,保证 $n-1$ 次操作后得到一棵以 $1$ 为根的树,且以后不会再出现 `F` 操作。   注意到 `A`,`B`,`C`,`F` 操作都有关于孩子顺序的规定,可以参照样例解释进行直观的理解。   共 $10$ 组数据。