题目描述

Vétyem Woods 中的山毛榉树 Ős Vezér 可建模为一棵包含 $N$ 个结点和 $N-1$ 条边的树。结点编号为 $0$ 到 $N-1$，边编号为 $1$ 到 $N-1$。边 $i$（$1 \le i < N$）连接结点 $i$ 和其父结点 $P[i]$（$0 \le P[i] < i$），且每条边有颜色 $C[i]$（颜色编号为 $1$ 到 $M$）。为方便，定义 $P[0] = -1$ 和 $C[0] = 0$（结点 $0$ 无父结点）。

子树定义

对结点 $r$（$0 \le r < N$），其子树 $T(r)$ 是满足以下条件的结点集合：

1. 结点 $r$ 属于 $T(r)$；
2. 若结点 $x$ 属于 $T(r)$，则 $x$ 的所有子结点也属于 $T(r)$；
3. 其他结点均不属于 $T(r)$。

$T(r)$ 的大小记为 $|T(r)|$。

绝妙置换与绝妙子树

对 $T(r)$ 中结点的置换 $v_0, v_1, \ldots, v_{|T(r)|-1}$，定义：

• 对 $1 \le i < |T(r)|$，$f(i)$ 为颜色 $C[v_i]$ 在序列 $C[v_1], C[v_2], \ldots, C[v_{i-1}]$ 中出现的次数（$f(1) = 0$，因序列为空）。

该置换是绝妙置换当且仅当：

1. $v_0 = r$；
2. 对 $1 \le i < |T(r)|$，结点 $v_i$ 的父结点是 $v_{f(i)}$（即 $P[v_i] = v_{f(i)}$）。

若 $T(r)$ 中存在某个绝妙置换，则称 $T(r)$ 是绝妙子树。注意，仅含单个结点的子树必为绝妙子树。

你的任务是判断树中每棵子树是否为绝妙子树，并返回结果数组。

实现细节

需在程序开始引入库 beechtree.h，并实现以下函数：

int[] beechtree(int N, int M, int[] P, int[] C)

参数说明

• $N$：树的结点总数；
• $M$：颜色总数；
• $P$：长度为 $N$ 的数组，$P[i]$ 是结点 $i$ 的父结点（$P[0] = -1$）；
• $C$：长度为 $N$ 的数组，$C[i]$ 是边 $i$ 的颜色（$C[0] = 0$）。

返回要求

返回长度为 $N$ 的数组 $b$，其中 $b[r] = 1$ 表示 $T(r)$ 是绝妙子树，$b[r] = 0$ 表示不是。每个测试用例中，该函数仅被调用一次。

例子

例子 1

函数调用：

beechtree(4, 2, [-1, 0, 0, 0], [0, 1, 1, 2])

树结构中，$T(1), T(2), T(3)$ 均为单结点子树（绝妙），$T(0)$ 无绝妙置换（非绝妙）。返回数组为 $[0, 1, 1, 1]$。

例子 2

函数调用对应题面中 $N=18$ 的树，返回数组为 $[0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$。

例子 3

函数调用对应 $N=7$ 的树，仅 $T(0)$ 非绝妙，返回数组为 $[0, 1, 1, 1, 1, 1, 1]$。

约束条件

• $3 \le N \le 200000$；
• $2 \le M \le 200000$；
• 对 $1 \le i < N$，$0 \le P[i] < i$ 且 $1 \le C[i] \le M$；
• $P[0] = -1$ 且 $C[0] = 0$。

子任务

子任务	附加限制	分值
1	$N \le 8$ 且 $M \le 500$	$9$
2	树为链状（$P[i] = i-1$ 对 $1 \le i < N$）	$5$
3	除结点 $0$ 外，所有结点的父结点为 $0$ 或父结点的父结点为 $0$	$9$
4	每种颜色的边至多 $2$ 条	$8$
5	$N \le 200$ 且 $M \le 500$	$14$
6	$N \le 2000$ 且 $M = 2$
7	$N \le 2000$	$12$
8	$M = 2$	$17$
9	无额外约束	$12$

评测程序示例

输入格式

1. 第 $1$ 行：$N \; M$；
2. 第 $2$ 行：$P[0] \; P[1] \; \ldots \; P[N-1]$；
3. 第 $3$ 行：$C[0] \; C[1] \; \ldots \; C[N-1]$。

输出格式

第 $1$ 行：函数返回的数组 $b$ 的元素，以空格分隔。