P7124 [Ynoi2008] stcm

w33z is a conscientious problem setter. Please use an efficient output method. This problem may require output up to 50 MB.

Given a tree, you can maintain a set that supports three operations: 1. Insert a node $x$ into the current set. 2. Undo the last insertion operation. 3. Mark the current set as the "subtree complement information" of node $i$. The subtree complement information of a node $x$ is defined as the set obtained by removing all nodes in the subtree of $x$ (including $x$ itself) from the set of all nodes in the tree. You must ensure that the subtree complement information for every node is correct.

**This problem contains multiple test cases.** For each test case: The first line contains a positive integer $n$. The next line contains $n - 1$ positive integers. The $i$-th number indicates that the parent of node $i + 1$ is node $j$, and it is guaranteed that $j < i + 1$. Read until EOF.

For each test case, output a string. From left to right: - Each substring of the form "+x" represents performing operation 1 on the node with index $x$. - Each substring "-" represents performing operation 2. - Each substring of the form "=x" represents performing operation 3 on the node with index $x$. - Each substring "!" indicates that all operations have ended. Any input after it will be ignored. The string must end with "!". No whitespace characters are allowed as separators in the output string.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078&nzhtl1477. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le T \le 3$. This problem uses Special Judge. The allowed number of operation 1 is $4.5 \times 10^6$. You are not allowed to insert an element that already exists in the current set. When there is no last insertion operation that has not been undone, operation 2 is not allowed. For each node, you must perform operation 3 **exactly once** on it. **The outputs of all test cases are checked independently.** Translated by ChatGPT 5