트리와 쿼리 19

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

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

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

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

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

둘째 줄에는 $1$번부터 $N$번 정점의 색을 나타내는 정수 $t_1, t_2, \cdots, t_N$이 주어진다. $t_i = 0$이면 검정색이고, $t_i = 1$이면 흰색이다.

셋째 줄에는 $2$번부터 $N$번 정점의 부모 정점을 나타내는 자연수 $P_2, P_3, \cdots, P_N$이 주어진다.

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

첫째 줄에는 초기 상태의 정답을 출력한다. 둘째 줄부터 $Q$개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.

• $2 \le N \le 5 \times 10^5$
• $1 \le Q \le 5 \times 10^5$
• $1 \le i \le N$에 대해 $0 \le t_i \le 1$
• $2 \le i \le N$에 대해 $1 \le P_i < i$
• $1 \le X \le N$