참나무

비템 숲은 다양한 색의 나무들이 있는 유명한 곳이다. 제일 오래되고 큰 참나무들 중 하나의 이름은 오스 베저이다.

오스 베저 트리는 $N$개의 정점과 $N-1$개의 간선으로 표현된다. 정점들은 $0$번부터 $N-1$번까지, 간선들은 $1$번부터 $N-1$번까지 번호가 붙어 있다. 각 간선은 두 개의 서로 다른 정점을 연결한다. 구체적으로 간선 $i$ ($1 \le i < N$)는 정점 $i$를 정점 $P[i]$ ($0 \le P[i] < i$)에 연결한다. 정점 $P[i]$를 정점 $i$의 부모라고 부르고 정점 $i$를 정점 $P[i]$의 자식이라고 부른다.

각 간선에는 색이 있다. 가능한 색은 $M$가지가 있고 $1$ 이상 $M$ 이하의 정수로 표현된다. 간선 $i$의 색은 $C[i]$이다. 서로 다른 간선의 색이 같을 수 있다.

주의: 위 정의에서 $i=0$인 경우에 해당하는 간선은 존재하지 않는다. 편의상 $P[0]=-1$과 $C[0]=0$으로 둔다.

예를 들어 오스 베저의 정점 수 $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]

아래 그림이 이 경우를 보여준다.

아르파드는 숲을 연구하는 친구인데 나무의 특정 부분인 서브트리를 연구하는 것을 좋아한다. 각 $r$ ($0 \le r < N$)에 대해 $r$의 서브트리는 정점들의 집합 $T(r)$로 아래와 같이 정의된다.

• 정점 $r$은 $T(r)$에 속한다.
• 어떤 정점 $x$가 $T(r)$에 속하면 $x$의 모든 자식도 $T(r)$에 속한다.
• 위에 언급한 정점들만 $T(r)$에 속한다.

집합 $T(r)$의 원소 수는 $|T(r)|$로 표현된다.

아르파드는 서브트리의 복잡하지만 재미있는 성질을 발견했다. 아르파드는 그 성질을 발견하기 위해 종이에 펜으로 많은 작업을 해 보았다. 이 문제를 푸는 사람도 그렇게 해야 할지도 모른다. 또 몇 가지 예제가 분석을 위해 주어질 것이다.

어떤 고정된 $r$에 대해 서브트리 $T(r)$의 정점들의 순열 $v_0,v_1,\ldots,v_{|T(r)|-1}$을 생각하자.

각 $i$ ($1 \le i < |T(r)|$)에 대해 $f(i)$를 색 $C[v_i]$가 다음 $i-1$개 색의 수열에 등장하는 횟수라고 하자.

$$C[v_1], C[v_2], \ldots, C[v_{i-1}]$$

항상 $f(1)=0$임에 주의하라. 왜냐하면 $f(1)$의 정의에 등장하는 색 번호의 수열이 비어 있기 때문이다.

순열 $v_0,v_1,\ldots,v_{|T(r)|-1}$은 다음 조건을 모두 만족할 때 아름다운 순열이라고 말한다.

• $v_0=r$.
• 각 $i$ ($1 \le i < |T(r)|$)에 대해 정점 $v_i$의 부모는 정점 $v_{f(i)}$이다.

각 $r$ ($0 \le r < N$)에 대해 $T(r)$에 있는 정점들의 아름다운 순열이 존재할 때, 그리고 그때에만 $T(r)$은 아름다운 서브트리라고 한다. 이 정의에 따르면 정점 하나로 구성된 서브트리는 항상 아름다운 서브트리이다.

위의 예제를 다시 보자. 서브트리들 $T(0)$과 $T(3)$은 아름답지 않다는 것을 보일 수 있다. 서브트리 $T(14)$는 정점 하나로 구성되므로 아름답다. 아래에서 서브트리 $T(1)$이 아름답다는 것을 보인다.

서로 다른 값들로 구성된 수열

$$[v_0,v_1,v_2,v_3,v_4,v_5,v_6]=[1,4,5,12,13,6,14]$$

을 보자. 이 수열은 $T(1)$에 있는 정점들의 순열이다. 그림에서 정점들에 붙어 있는 레이블들은 각 정점이 순열에서 나타나는 위치를 표현한다.

이제 이 수열이 아름답다는 것을 보일 것이다.

• $v_0=1$.
• $f(1)=0$이다. 왜냐하면 $C[v_1]=C[4]=1$은 $[]$에 $0$번 등장하기 때문이다. 그리고 $v_1$의 부모는 $v_0$이다. 즉, 정점 $4$의 부모는 정점 $1$이다. (엄밀하게는 $P[4]=1$이다.)
• $f(2)=0$이다. 왜냐하면 $C[v_2]=C[5]=2$는 $[1]$에 $0$번 등장하기 때문이다. 그리고 $v_2$의 부모는 $v_0$이다. 즉, 정점 $5$의 부모는 정점 $1$이다.
• $f(3)=1$이다. 왜냐하면 $C[v_3]=C[12]=1$은 $[1,2]$에 $1$번 등장하기 때문이다. 그리고 $v_3$의 부모는 $v_1$이다. 즉, 정점 $12$의 부모는 정점 $4$이다.
• $f(4)=1$이다. 왜냐하면 $C[v_4]=C[13]=2$는 $[1,2,1]$에 $1$번 등장하기 때문이다. 그리고 $v_4$의 부모는 $v_1$이다. 즉, 정점 $13$의 부모는 정점 $4$이다.
• $f(5)=0$이다. 왜냐하면 $C[v_5]=C[6]=3$은 $[1,2,1,2]$에 $0$번 등장하기 때문이다. 그리고 $v_5$의 부모는 $v_0$이다. 즉, 정점 $6$의 부모는 정점 $1$이다.
• $f(6)=2$이다. 왜냐하면 $C[v_6]=C[14]=2$는 $[1,2,1,2,3]$에 $2$번 등장하기 때문이다. 그리고 $v_6$의 부모는 $v_2$이다. 즉, 정점 $14$의 부모는 정점 $5$이다.

$T(1)$에 있는 정점들의 아름다운 순열을 찾을 수 있으므로 서브트리 $T(1)$은 아름답다.

아르파드를 도와 오스 베저의 서브트리들 각각에 대해 아름다운지의 여부를 판단하는 프로그램을 작성하라.

구현 세부사항

다음 함수를 작성해야 한다.

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

• $N$: 트리의 정점 개수
• $M$: 가능한 색의 개수
• $P$, $C$: 간선들을 표현한 크기 $N$인 배열들
• 이 함수는 크기 $N$인 배열 $b$를 리턴해야 한다. 각 $r$ ($0 \le r < N$)에 대해 $b[r]$은 $T(r)$가 아름다운 경우 $1$, 아닌 경우 $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

다음 호출을 보자.

beechtree(18, 3,
          [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11],
          [ 0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2,  1,  2,  3])

해당하는 트리는 본문의 예제와 같다.

이 호출은 $[0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]$을 리턴해야 한다.

예제 3

다음 호출을 보자.

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

해당하는 트리는 아래 그림과 같다.

이 경우 $T(0)$이 유일하게 아름답지 않은 서브트리이다. 이 호출은 $[0,1,1,1,1,1,1]$을 리턴해야 한다.

제약 조건

• $3 \le N \le 200\,000$
• $2 \le M \le 200\,000$
• $0 \le P[i] < i$ (각 $i$ ($1 \le i < N$)에 대해)
• $1 \le C[i] \le M$ (각 $i$ ($1 \le i < N$)에 대해)
• $P[0]=-1$이고 $C[0]=0$

서브태스크

1. (9점) $N \le 8$이고 $M \le 500$.
2. (5점) 간선 $i$는 정점 $i$와 $i-1$을 연결한다. 즉, 각 $i$ ($1 \le i < N$)에 대해 $P[i]=i-1$이다.
3. (9점) 정점 $0$을 제외한 각 정점은 정점 $0$에 바로 연결되어 있거나 정점 $0$에 바로 연결된 정점에 바로 연결되어 있다. 즉, 각 $i$ ($1 \le i < N$)에 대해 $P[i]=0$ 혹은 $P[P[i]]=0$이 성립한다.
4. (8점) 각 $c$ ($1 \le c \le M$)에 대해 색이 $c$인 간선은 최대 두 개 존재한다.
5. (14점) $N \le 200$이고 $M \le 500$.
6. (14점) $N \le 2\,000$이고 $M=2$.
7. (12점) $N \le 2\,000$.
8. (17점) $M=2$.
9. (12점) 추가적인 제한이 없다.

line 1: N M
line 2: P[0] P[1] ... P[N - 1]
line 3: C[0] C[1] ... C[N - 1]

beechtree가 리턴한 배열의 원소들이 $b[0],b[1],\ldots$라고 하자.

샘플 그레이더는 아래의 내용을 한 줄에 출력한다.

line 1: b[0] b[1] ...