#P7124. [Ynoi2008] stcm

[Ynoi2008] stcm

题目背景

w33z 是良心出题人!

请使用高效输出方式,本题最多需要输出 50MB。

题目描述

给定一棵树,你可以维护一个集合,支持三种操作:

  1. 当前集合中插入一个节点 xx
  2. 撤回上一次插入操作
  3. 将当前点集标为第 ii 个点的子树补信息

一个点 xx 的子树补信息定义为,树的点集除去 xx 的子树(包括 xx)内的点得到的集合; 需要保证每个点的子树补信息都是正确的。

输入格式

本题输入含有多组测试数据。

一组测试数据格式为:

第一行一个正整数 nn

之后一行 n1n-1 个正整数,第 ii 个数表示 i+1i+1 节点的父亲节点 jj,保证 j<i+1j<i+1

请读入至 EOF。

输出格式

对每一组数据,输出一个字符串,从左往右,每个"+x"形式的子串代表进行一次 1 操作,对象为编号 xx 的节点,每个"-"子串代表进行一次 2 操作,每个"=x"形式的子串代表进行一次 3 操作,对象为编号 xx 的节点,每个"!"子串代表全部操作都已结束,在其后面的任何输入会被忽略,字符串必须以"!"表示结束。

输出的字符串中不允许以任何空白字符分隔。

6
1 1 2 3 3
6
1 1 2 3 3
=1+1+3+5+6=2+2=4----+4+2=3+3+6=5-+5=6!
=1+1+3+5+6=2+2=4----+4+2=3+3+6=5-+5=6!

提示

Idea:nzhtl1477,Solution:ccz181078,Code:ccz181078,Data:ccz181078&nzhtl1477

对于 100%100\% 的数据,满足 1n1051\le n\le 10^51T31\le T\le 3

题目采用 Special Judge 评测。

允许进行的 1 操作次数为 4.5×1064.5 \times 10^6 次,不允许插入一个当前集合中存在的元素。

当最后一次未被撤回的插入操作不存在时,不允许进行 2 操作。

对每个点,必须对其进行恰好一次 3 操作。

所有测试数据输出独立检验。