시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 9 7 7 77.778%

문제

N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 모든 정점의 색은 검정색 또는 흰색이다.

아래의 쿼리를 처리하는 프로그램을 작성하시오.

  • X : X번 정점의 색을 바꾼다. (흰색 -> 검정색, 검정색 -> 흰색) 이후 서로 다른 모든 흰색 정점 쌍 (a,b)에 대해 LCA(최소 공통 조상)레벨의 합을 출력한다.

루트 정점은 1번 정점이다. 루트 정점의 레벨은 0이며, 다른 정점의 레벨은 (부모 정점의 레벨) + 1로 정의한다.

입력

첫째 줄에 정점의 갯수 N과 쿼리의 갯수 Q가 주어진다.

뚤째 줄에는 1, 2, ⋯, N번 정점의 색을 나타내는 정수 t1, t2, ⋯, tN이 주어진다. 1 ≤ i ≤ N인 자연수 i에 대해 t= 0인 경우 검정색이고 t= 1인 경우 흰색이다.

셋째 줄에는 2, 3, ⋯, N번 정점의 부모 정점을 나타내는 자연수 P2, P3, ⋯, PN이 주어진다.

다음 Q개의 줄에는 쿼리를 나타내는 X가 주어진다.

출력

첫번째 줄에는 초기 상태의 정답을 출력한다.

두번째 줄부터 Q개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.

제한

  • 2 ≤ N ≤ 5 × 105
  • 1 ≤ Q ≤ 5 × 105
  • 1 ≤ i ≤ N에 대해 0 ≤ t≤ 1
  • 2 ≤ i ≤ N에 대해 1 ≤ P< i
  • 1 ≤ X ≤ N
     

예제 입력 1

5 5
1 0 0 1 1
1 1 3 2
5
3
5
4
2

예제 출력 1

0
0
1
1
0
1

예제 입력 2

10 10
1 0 0 1 1 0 1 0 1 0
1 2 1 4 5 6 1 4 1
8
4
4
4
10
9
2
1
5
3

예제 출력 2

7
7
4
7
4
4
2
2
2
0
1

예제 입력 3

20 20
1 0 1 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0
1 2 3 4 2 2 1 3 2 4 4 3 3 3 8 14 11 7 7
5
12
19
5
10
18
17
13
10
5
5
13
10
4
11
8
14
13
19
15

예제 출력 3

26
16
26
21
33
39
26
38
51
44
31
44
32
38
53
71
71
55
70
79
97

출처