{"raw_statement":[{"iden":"background","content":"这是一道交互题，你只需要实现代码中要求的函数。\n\n你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。\n\n本题仅支持 C++ 语言提交。"},{"iden":"statement","content":"Vétyem Woods 是一片著名的缤纷多彩的森林。其中最老最高的一棵山毛榉树叫 Ős Vezér。\n\n树 Ős Vezér 可以被建模成 $N$ 个**结点**和 $N-1$ 条**边**的集合。结点的编号为从 $0$ 到 $N-1$，边的编号为从 $1$ 到 $N-1$。每条边均连接树上两个不同的结点。具体地说，边 $i$（$1 \\le i \\lt N$）从结点 $i$ 连接到结点 $P[i]$，这里 $0 \\le P[i] \\lt i$。结点 $P[i]$ 被称为是结点 $i$ 的**父结点**，而结点 $i$ 被称为是结点 $P[i]$ 的一个**子结点**。\n\n每条边都有某种颜色。一共有 $M$ 种可能的颜色，编号为从 $1$ 到 $M$。边 $i$ 的颜色为 $C[i]$。不同的边可能有相同的颜色。\n\n注意，在上面的定义中，$i = 0$ 的情形并不对应树上的边。方便起见，我们令 $P[0] = -1$ 和 $C[0] = 0$。\n\n例如，假定 Ős Vezér 有 $N = 18$ 个结点和 $M = 3$ 种可能的颜色，以及 $17$ 条边。边的描述为 $P = [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11]$，边的颜色为 $C = [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3]$。这棵树如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/xnxdhpz1.png)\n\nÁrpád 是一位才华横溢的护林人，他喜欢研究树上被称为**子树**的部分。\n对所有满足 $0 \\le r \\lt N$ 的  $r$，结点 $r$ 的子树是一个满足以下性质的结点集合 $T(r)$：\n\n* 结点 $r$ 属于 $T(r)$。\n* 如果某个结点 $x$ 属于 $T(r)$，则 $x$ 的所有子结点都属于$T(r)$。\n* 除了上述情况以外，其他结点都不属于 $T(r)$。\n\n集合 $T(r)$ 的大小记作 $|T(r)|$。\n\nÁrpád 最近发现了一个复杂但有趣的子树性质。Árpád 的发现需要用到大量的纸和笔做演算，他认为你需要做同样的事情才能完成理解。他还会给你几个例子，让你能够对它们做详细的分析。\n\n假设我们有某个给定的 $r$，以及子树 $T(r)$ 中结点的某个置换 $v_0, v_1, \\ldots, v_{|T(r)|-1}$。\n\n对于所有满足 $1 \\le i \\lt |T(r)|$ 的 $i$，令 $f(i)$ 为颜色 $C[v_i]$ 在长为 $i-1$ 的颜色序列 $C[v_1], C[v_2], \\ldots, C[v_{i-1}]$ 中的出现次数。\n\n（注意，$f(1)$ 必定为 $0$，原因是其定义中要考察的颜色序列是空的。）\n\n置换 $v_0, v_1, \\ldots, v_{|T(r)|-1}$ 被称为是一个**绝妙置换**，当且仅当以下性质成立：\n\n* $v_0 = r$。\n* 对于所有满足 $1 \\le i \\lt |T(r)|$ 的 $i$，结点 $v_i$ 的父结点是 $v_{f(i)}$。\n\n对于所有满足 $0 \\le r \\lt N$ 的 $r$，子树 $T(r)$ 是一棵**绝妙子树**，当且仅当 $T(r)$ 中结点存在某个绝妙置换。注意，根据定义，仅包含单独一个结点的子树都是绝妙的。\n\n考虑上面给出的树的例子。可以看到，子树 $T(0)$ 和 $T(3)$ 不是绝妙的。子树 $T(14)$ 是绝妙的，因为它仅包含一个结点。接下来，我们将要说明子树 $T(1)$ 也是绝妙的。\n\n考虑一个由不同整数构成的序列 $[v_0, v_1, v_2, v_3, v_4, v_5, v_6] = [1, 4, 5, 12, 13, 6, 14]$。这个序列是 $T(1)$ 中结点的一个置换。下图给出了这个置换。序列中每个结点旁边的数字，是该结点在置换中的索引。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ziecuezc.png)\n\n我们将要验证，这是一个**绝妙置换**。\n\n* $v_0 = 1$。\n* $f(1) = 0$，原因是 $C[v_1] = C[4] = 1$ 在序列 $[\\,]$ 中出现了 $0$ 次。\n * 相应地，$v_1$ 的父结点是 $v_0$。也就是说，$4$ 的父结点是 $1$。（形式化地，$P[4] = 1$。）\n* $f(2) = 0$，原因是 $C[v_2] = C[5] = 2$ 在序列 $[1]$ 中出现了 $0$ 次。\n * 相应地，$v_2$ 的父结点是 $v_0$。也就是说，$5$ 的父结点是 $1$。\n* $f(3) = 1$，原因是 $C[v_3] = C[12] = 1$ 在序列 $[1, 2]$ 中出现了 $1$ 次。\n * 相应地，$v_3$ 的父结点是 $v_1$。也就是说，$12$ 的父结点是 $4$。\n* $f(4) = 1$，原因是 $C[v_4] = C[13] = 2$ 在序列 $[1, 2, 1]$ 中出现了 $1$ 次。\n * 相应地，$v_4$ 的父结点是 $v_1$。也就是说，$13$ 的父结点是 4。\n* $f(5) = 0$，原因是 $C[v_5] = C[6] = 3$ 在序列 $[1, 2, 1, 2]$ 中出现了 $0$ 次。\n * 相应地，$v_5$ 的父结点是 $v_0$。也就是说，$6$ 的父结点是 $1$。\n* $f(6) = 2$，原因是 $C[v_6] = C[14] = 2$ 在序列 $[1, 2, 1, 2, 3]$ 中出现了  $2$ 次。\n * 相应地，$v_6$ 的父结点是 $v_2$。也就是说，$14$ 的父结点是 $5$。\n\n由于我们能为 $T(1)$ 中的结点找到一个**绝妙置换**，子树 $T(1)$ 因此是一棵**绝妙子树**。\n\n你的任务是，帮助 Árpád 确定 Ős Vezér 的每棵子树是否是绝妙的。"},{"iden":"input","content":"你需要实现以下函数。\n\n```\nint[] beechtree(int N, int M, int[] P, int[] C)\n```\n\n* $N$：树中的结点数量。\n* $M$：树中边的可能颜色的数量。\n* $P$，$C$：长度为 $N$ 的两个数组，以描述树中的边。\n* 该函数应当返回长度为 $N$ 的某个数组 $b$。 \n  对所有满足 $0 \\le r \\lt N$ 的 $r$，如果 $T(r)$ 是绝妙的，则 $b[r]$ 应为 $1$，否则应为 $0$。\n* 该函数在每个测试用例上恰好被调用一次。"},{"iden":"note","content":"\n\n### 样例\n\n#### 样例 1\n\n考虑如下调用：\n\n```\nbeechtree(4, 2, [-1, 0, 0, 0], [0, 1, 1, 2])\n```\n\n这棵树如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/bcv1naft.png)\n\n$T(1)$，$T(2)$ 和 $T(3)$ 均各自包含单独一个结点，因此都是绝妙的。\n$T(0)$ 不是绝妙的。\n因此，函数应当返回 $[0, 1, 1, 1]$。\n\n#### 样例 2\n\n考虑如下调用：\n\n```\nbeechtree(18, 3, \n          [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11],\n          [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3])\n```\n\n这个例子在题面中已经给出。\n\n函数应当返回 $[0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$。\n\n#### 样例 3\n\n考虑如下调用：\n\n```\nbeechtree(7, 2, [-1, 0, 1, 1, 0, 4, 5], [0, 1, 1, 2, 2, 1, 1])\n```\n\n该例子如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/cv6ljl13.png)\n\n$T(0)$ 是唯一不是绝妙的子树。函数应当返回 $[0, 1, 1, 1, 1, 1, 1]$。\n\n### 约束条件\n\n* $3 \\le N \\le 200\\,000$\n* $2 \\le M \\le 200\\,000$\n* $0 \\le P[i] \\lt i$（对于所有满足 $1 \\le i \\lt N$ 的 $i$）\n* $1 \\le C[i] \\le M$（对于所有满足 $1 \\le i \\lt N$ 的 $i$）\n* $P[0] = -1$ 且 $C[0] = 0$\n\n### 子任务\n\n1. （9 分）$N \\le 8$ 且 $M \\le 500$\n1. （5 分）边 $i$ 从结点 $i$ 连接到结点 $i-1$。也就是说，对所有满足 $1 \\le i \\lt N$ 的 $i$，都有 $P[i] = i-1$。\n1. （9 分）除了结点 $0$ 以外，其他结点要么连接到结点 $0$，要么连接到某个连接到结点 $0$ 的结点。\n    也就是说，对于所有满足 $1 \\le i \\lt N$ 的 $i$，要么有 $P[i]=0$，要么有 $P[P[i]]=0$。\n1. （8 分）对于所有满足 $1 \\le c \\le M$ 的 $c$，至多有两条边的颜色为 $c$。\n1. （14 分） $N \\le 200$ 且 $M \\le 500$\n1. （14 分） $N \\le 2\\,000$ 且 $M = 2$\n1. （12 分） $N \\le 2\\,000$\n1. （17 分） $M = 2$\n1. （12 分） 没有额外的约束条件。\n\n### 评测程序示例\n\n评测程序示例按以下格式读取输入：\n\n* 第 $1$ 行：$N \\; M$\n* 第 $2$ 行：$P[0] \\; P[1] \\; \\ldots \\; P[N-1]$\n* 第 $3$ 行：$C[0] \\; C[1] \\; \\ldots \\; C[N-1]$\n\n令 $b[0], \\; b[1], \\; \\ldots$ 表示 `beechtree` 所返回的数组中的元素。评测程序示例以如下格式，在单行中输出你的答案：\n* 第 $1$ 行：$b[0] \\; b[1] \\; \\ldots$"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}