#P18874. [IIOT2017]Masters and Slaves
[IIOT2017]Masters and Slaves
题目描述
William 将 台计算机组成一棵以计算机 为根的树。计算机的编号为 ,计算机 的父节点为 ,其中 。
由于某些计算机负担过重,William 会加入新的代理计算机,并重新分配一些连接。每次调整给出一台计算机 ,以及 台互不相同的计算机 。调整方式如下:
- 创建一台新代理计算机。第 次调整创建的计算机编号为 ,其中 从 开始。
- 断开每台 与其原父节点之间的连接,并将它们的父节点改为新代理。没有被修改的父子连接保持不变。
- 将新代理的父节点设为 。
和 可以是之前创建的代理计算机; 也可以为 。
例如,在下图左侧的网络中,将计算机 改为新代理 的孩子,再将 连接到计算机 ,就得到右侧的网络。

树的高度是从根到任意节点所经过的边数的最大值。例如,上图中调整前的高度为 ,调整后的高度为 。
每次调整后,你需要判断网络是否出现环。如果没有环,则判断树的高度是否比本次调整前更大。一旦出现环,立即停止处理剩余的调整。
输入格式
第一行包含两个整数 ,分别表示初始计算机数量和计划进行的调整次数。
第二行包含 个整数 ,表示初始网络中每台计算机的父节点。
接下来 行依次描述每次调整。每行首先包含两个整数 ,随后包含 个整数 。
输出格式
输出一行字符串,每个字符对应一次实际执行的调整:
c:本次调整产生了环。输出该字符后立即结束。1:没有产生环,并且树高比本次调整前增大了。0:没有产生环,并且树高没有增大,包括树高不变或减小的情况。
若所有调整都未产生环,字符串长度为 ;否则,字符串在第一次产生环的位置结束,最后一个字符为 c。
数据范围
- 。
- 。
- ,对于 ,有 。
- 初始网络是一棵以 为根的树。
- 每次调整中,,所选的 互不相同。
- 在第 次调整中, 和每个 均为当时已经存在的计算机编号,即 。
- 在尚未产生环时,树的高度不超过 。
样例 1
3 5
-1 0 0
0 2 1 2
3 0
2 2 4 3
1 1 0
6 5 4 2 3 1 5
10c
样例 1 解释
前三次调整的过程如下图所示。第三次调整产生环,因此不再处理第四、第五次调整。

样例 2
8 4
-1 0 0 2 2 2 2 1
2 3 5 6 7
2 2 5 4
8 2 6 7
1 0
1010
样例 2 解释
下图依次展示初始网络和四次调整后的网络。树高依次为 。
