AC 오토마톤

JB는 AC 오토마톤으로 문제에서 "AC"를 더 많이 얻으려 한다.

AC 오토마톤은 노드 $n$개로 이루어진 루트 트리이며, 루트는 1번 노드다. 루트를 제외한 각 노드 $i$에는 고유한 부모 $p\_i$와 문자 $s\_i$가 있다. 문자는 'A', 'C', '?' 중 하나다. 노드 $x$가 $y$의 조상이라는 것은 $x = p\_y$이거나, $x$가 $p\_y$의 조상인 경우를 말한다. JB가 얻는 "AC"의 개수는 순서쌍 $(x,y)$ 중 $x$가 $y$의 조상이고, $s\_x$가 'A', $s\_y$가 'C'인 쌍의 수와 같다. JB는 각 '?'를 'A' 또는 'C'로 바꿀 수 있다. 목표는 모든 '?'를 바꾼 뒤 "AC"의 개수를 최대로 만드는 것이다.

문제는 계속 바뀐다. JB는 AC 오토마톤을 $q$번 바꾼다. 매번 노드 $x$의 문자를 'A', 'C', '?' 중 하나로 고친다(바뀌지 않을 수도 있다). 각 변경 후에, 모든 '?'를 바꿨을 때 얻을 수 있는 "AC"의 최대 개수를 구하라. JB는 최댓값을 계산하는 동안 실제로 오토마톤을 고치지 않는다. 예시를 참고하라.

첫 번째 줄에 정수 $n$과 $q$가 주어진다 ($1\le n, q\le 300\ 000$).

두 번째 줄에는 각 노드의 문자를 나타내는 길이 $n$의 문자열이 주어진다. 모든 문자는 'A', 'C', '?' 중 하나다.

세 번째 줄에는 $n - 1$개의 정수가 주어진다. $i$번째 정수 $p\_i$ ($1\le p\_i \le i$)는 노드 $i+1$의 부모다.

다음 $q$개의 줄은 수정을 나타낸다. $i$번째 줄에는 정수 $x$ ($1\le x\le n$)와 문자 $y$ ($y$는 'A', 'C', '?' 중 하나)가 주어지며, 이는 노드 $x$의 문자를 $y$로 바꾼다는 뜻이다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 수정 후 "AC"의 최대 개수를 정수 하나로 출력한다.

첫 번째 수정 후 최적의 치환 중 하나는 "ACCCC"이며, 이때 순서쌍은 4개다: (1,2), (1,3), (1,4), (1,5).

두 번째 수정 후 최적의 치환 중 하나는 "ACCAC"이며, 이때 순서쌍은 3개다: (1,2), (1,3), (1,5).

세 번째 수정 후 최적의 치환 중 하나는 "AACAC"이며, 이때 순서쌍은 3개다: (1,3), (2,3), (1,5).