P4693 [Ynoi Easy Round 2016] Zhabolong II

In an instant… If I really had to say, it was even shorter than an instant. Usaki flew toward the cliff. Small and thin Usaki flew over the cliff more easily than I had imagined. I hurriedly ran to the edge of the cliff. However, after rushing out at full speed, it was not so easy to change direction. I lost my balance and fell to the ground. I could only keep chasing Usaki’s figure with my eyes. Usaki, who had flown out over the cliff. Her body floated in midair. In the next moment, she gave herself to the law of free fall… and dropped straight down the steep cliff.  Those narrow eyes… staring into my eyes. Is this an illusion… or reality… Takuji’s fingertips pierced through the skull… This is impossible… how could a person’s hand strength crush a skull… This is undoubtedly an illusion… it cannot exist in reality… As someone who practices martial arts, I know this best… Something that is fundamentally impossible… Even so… My consciousness still began to blur… I could no longer keep in touch with this world… “I… have taken in big brother Minamori’s body…”  A familiar scenery. Even more familiar than what I saw before. A scenery I know…  “I will take him away… so you should go…” “Takuji… that ‘denpa kid’, I’ll take him away…” “So you go forward…” “At the end of the slope that cannot be climbed” “You cannot stop here, you must go to meet little Yuu” “Alright, cheer up… Minamori” “Let’s say goodbye here…”  A light, floating feeling. In an instant, I felt the air around rapidly turn cold. The dust that was kicked up was lit by moonlight, drifting in the air. Saying farewell to the parallel lines that would never intersect, Usaki and I were pulled into… A world of vertical falling. The moonlight outlined Usaki’s body. There were no shadows on the ground. As if flying high in the sky… In the distance, the sound of sirens came. Echoing again and again beneath the blue sky. I looked up at the endless sky and fell straight down. Not letting her out of my sight even for a moment, Usaki above me… The moon was laughing. God was laughing. Laughing at this ridiculous posture. Laughing at this tragedy like a comedy. The stars spun. Dancing and swaying. The god in the night sky was mocking us. Like an innocent child who wants to throw an empty bottle onto the ground… The world became completely empty.  A slope with no end in sight… A distant and blurry slope… As if… we were strolling in such a world… Even if you care about what lies ahead of the slope, it is of no use. We just walk happily on this slope. 

You are playing a galgame, and suddenly you hear that the Soviet Union has collapsed. So you realize that you will never see a living Soviet person again. Feeling depressed, you start writing a data structure problem: This is a simulation problem. You need to maintain a rooted ordered tree with $n$ nodes (that is, the children of each node have a left-to-right order). Initially, the root is $1$. You need to support the following operations: `A(x,y)`: Perform path compression on $x$, i.e., for every node on the path from $x$ to the root except the root, set its parent to the root. The order of these nodes among the root’s children remains the same as their order on the original path from shallow to deep. `B(x,y)`: Take the root’s children $x,y$ ($x$ is to the left of $y$) and all nodes between them, and expand them in order into a single path. $x$ remains connected to the root. All children that these involved nodes originally had are moved to the right side of the path. `C(x,y)`: Set the root of the tree to be $x$. At this time, nodes that were on the left side of the original path from the old root to $x$ remain on the left and their relative order does not change; similarly for the right side. After $x$ becomes the root, the children of $x$ are placed on the right side of the path from $x$ to the original root. `D(x,y)`: Add a number to the weight of every node on the path from $x$ to the root, and then query the sum of weights on the path from $x$ to the root. `E(x,y)`: It is guaranteed that $x$ and $y$ have the same parent and that $x$ is to the left of $y$. For every node between $x$ and $y$ (including $x,y$) among the children of $x$’s parent, add $x+y$ to its weight, and then query the sum of weights of these nodes. `F(x,y)`: Add $y$ as a child of $x$, at the far right. This operation is performed before all other operations and is used to describe the initial shape of the tree.

The first line contains two integers $n,q$, representing the number of nodes in the tree and the number of operations. The next $q$ lines each describe an operation.

For each `D` or `E` operation, output one line: the result modulo $2^{32}$.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078 Constraints: $2\leq n\leq 10^5$，$n\leq q\leq 2\times 10^5$，$0\leq x,y \leq n$. All operations are guaranteed to be valid. For symmetry, all operations have two parameters $x,y$, but actually $y$ is not needed in operations `A` and `C`. The testdata guarantees that $y=0$ in these cases. The first $n-1$ operations are all `F` operations, guaranteeing that after these $n-1$ operations you get a tree rooted at $1$, and no more `F` operations will appear afterwards. Note that operations `A`, `B`, `C`, and `F` all have rules about the order of children. You may refer to the sample explanation for an intuitive understanding. There are $10$ test groups. Translated by ChatGPT 5