#P18874. [IIOT2017]Masters and Slaves

[IIOT2017]Masters and Slaves

题目描述

William 将 NN 台计算机组成一棵以计算机 00 为根的树。计算机的编号为 0,1,…,N−10,1,\ldots,N-1,计算机 ii 的父节点为 MiM_i,其中 M0=−1M_0=-1。

由于某些计算机负担过重,William 会加入新的代理计算机,并重新分配一些连接。每次调整给出一台计算机 CC,以及 KK 台互不相同的计算机 S0,S1,…,SK−1S_0,S_1,\ldots,S_{K-1}。调整方式如下:

  1. 创建一台新代理计算机。第 ii 次调整创建的计算机编号为 N+i−1N+i-1,其中 ii 从 11 开始。
  2. 断开每台 SjS_j 与其原父节点之间的连接,并将它们的父节点改为新代理。没有被修改的父子连接保持不变。
  3. 将新代理的父节点设为 CC。

CC 和 SjS_j 可以是之前创建的代理计算机;KK 也可以为 00。

例如,在下图左侧的网络中,将计算机 5,6,75,6,7 改为新代理 88 的孩子,再将 88 连接到计算机 22,就得到右侧的网络。

调整前后的网络

树的高度是从根到任意节点所经过的边数的最大值。例如,上图中调整前的高度为 22,调整后的高度为 33。

每次调整后,你需要判断网络是否出现环。如果没有环,则判断树的高度是否比本次调整前更大。一旦出现环,立即停止处理剩余的调整。

输入格式

第一行包含两个整数 N,EN,E,分别表示初始计算机数量和计划进行的调整次数。

第二行包含 NN 个整数 M0,M1,…,MN−1M_0,M_1,\ldots,M_{N-1},表示初始网络中每台计算机的父节点。

接下来 EE 行依次描述每次调整。每行首先包含两个整数 C,KC,K,随后包含 KK 个整数 S0,S1,…,SK−1S_0,S_1,\ldots,S_{K-1}。

输出格式

输出一行字符串,每个字符对应一次实际执行的调整:

  • c:本次调整产生了环。输出该字符后立即结束。
  • 1:没有产生环,并且树高比本次调整前增大了。
  • 0:没有产生环,并且树高没有增大,包括树高不变或减小的情况。

若所有调整都未产生环,字符串长度为 EE;否则,字符串在第一次产生环的位置结束,最后一个字符为 c。

数据范围

  • 1≤N≤1 000 0001\le N\le 1\,000\,000。
  • 1≤E≤10 0001\le E\le 10\,000。
  • M0=−1M_0=-1,对于 1≤i<N1\le i<N,有 0≤Mi<N0\le M_i<N。
  • 初始网络是一棵以 00 为根的树。
  • 每次调整中,0≤K≤1000\le K\le100,所选的 SjS_j 互不相同。
  • 在第 ii 次调整中,CC 和每个 SjS_j 均为当时已经存在的计算机编号,即 0≤C,Sj<N+i−10\le C,S_j<N+i-1。
  • 在尚未产生环时,树的高度不超过 100100。

样例 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 解释

前三次调整的过程如下图所示。第三次调整产生环,因此不再处理第四、第五次调整。

样例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 解释

下图依次展示初始网络和四次调整后的网络。树高依次为 2,3,3,4,42,3,3,4,4。

样例2的网络变化