#pragma GCC optimize("Ofast")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ott(i,l,r) for (int i = l; i <= r; i ++)
#define tto(i,l,r) for (int i = r; i >= l; i --)
using namespace std;
using ll = long long;
int read () {
int x = 0; bool f = 0; char c = getchar ();
while (!isdigit (c)) f |= (c == '-'), c = getchar ();
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
if (f) x = -x; return x;
}
const int N = 3e5 + 110, inf = 0x3f3f3f3f;
int n, m, q, idx, B;
ll res;
vector <int> e[N], E[N];
int up[N], dn[N];
int dfn[N], dep[N], fa[N];
int lg[N << 1], f[N << 1][20];
char ch[N];
void dfs0 (int u) {
f[dfn[u] = ++ idx][0] = u, dep[u] = dep[fa[u]] + 1;
for (int v : e[u]) {
dfs0 (v);
f[++ idx][0] = u;
}
return ;
}
int lca (int x, int y) {
x = dfn[x], y = dfn[y];
if (x > y) swap (x, y);
int z = lg[y - x + 1], f1 = f[x][z], f2 = f[y - (1 << z) + 1][z];
return dep[f1] < dep[f2] ? f1 : f2;
}
struct OPT {
int x; char c;
} a[N];
struct BLOCK {
int ac, now, val, sum, len;//ac = 'A'count
vector <int> p; pair <int, int> *a;
void ins (int v) {
if (v >= 0) ++ sum;
if (-m <= v && v <= m) p.pb (v);
return ;
}
void init () {
sort (p.begin (), p.end ()); a = new pair <int, int>[p.size () + 4];
a[0] = {-inf, 0};
for (int v : p) {
if (v != a[len].fi) a[++ len] = {v, 1};
else ++ a[len].se;
if (len && v >= 0) now = len;
}
a[++ len] = {inf, 0};
return ;
}
void upd (int i) {
if (ch[i] == 'A') ++ ac;
if (ch[i] == '?') ins (dn[i] - up[i]);
return ;
}
void add (int v) {
if (v == 1) {
if (a[now].fi == val ++) sum -= a[now ++].se;
res -= 1ll * sum;
}
if (v == -1) {
res += 1ll * sum;
if (a[now - 1].fi == -- val) sum -= a[-- now].se;
}
return ;
}
void clear () {
ac = now = val = sum = len = 0;
vector <int> ().swap (p); free (a);
return ;
}
} b[N];
int id[N], val[N], FA[N];
bool cmp (int x, int y) {
return dfn[x] < dfn[y];
}
void push (int u, int z) {
b[z].upd (u);
for (int v : e[u]) push (v, z);
return ;
}
int Z, OTH;
void find (int x) {
if (id[fa[x]]) {
val[Z = id[x] = ++ idx] = x;
return ;
}
find (fa[x]);
b[Z].upd (fa[x]);
for (int v : e[fa[x]]) {
if (v == x) continue;
if (!OTH) val[OTH = id[v] = ++ idx] = v;
push (v, OTH);
}
return ;
}
void red (int u) {
dn[u] = 0;
for (int v : e[u]) {
up[v] = up[u] + (ch[u] != 'C');
red (v);
dn[u] += dn[v] + (ch[v] != 'A');
}
if (ch[u] == 'A') res += 1ll * dn[u];
if (ch[u] == '?') res += 1ll * max (0, dn[u] - up[u]);
return ;
}
void cup (int u, int V) {
for (int v : E[u]) {
if (val[v] < 0) {
int tv = -val[v];
if (ch[tv] == '?') res -= 1ll * max (0, dn[tv] - up[tv]);
up[tv] += V;
if (ch[tv] == '?') res += 1ll * max (0, dn[tv] - up[tv]);
}
else {
b[v].add (V);
}
cup (v, V);
}
return ;
}
void cdn (int u, int V) {
if (!u) return ;
if (val[u] < 0) {
int tu = -val[u];
if (ch[tu] == '?') res -= 1ll * max (0, dn[tu] - up[tu]);
dn[tu] += V; if (ch[tu] == 'A') res += 1ll * V;
if (ch[tu] == '?') res += 1ll * max (0, dn[tu] - up[tu]);
}
else {
b[u].add (-V), res += 1ll * b[u].ac * V;
}
cdn (FA[u], V);
return ;
}
void sol () {
ott (i, 1, m) val[++ idx] = a[i].x;
sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
sort (val + 1, val + 1 + idx, cmp);
ott (i, 2, idx) val[idx + i - 1] = lca (val[i - 1], val[i]); val[idx += idx] = 1;
sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
ott (i, 1, idx) {
id[val[i]] = i;
val[i] = -val[i];//区分会修改的点
}
ott (i, 2, idx) {
if (val[i] > 0) break;
if (!id[fa[-val[i]]]) {
OTH = Z = 0, find (-val[i]);
if (OTH) E[FA[OTH] = i].pb (OTH);
E[FA[Z] = id[fa[val[Z]]]].pb (Z), E[FA[i] = Z].pb (i);
}
else E[FA[i] = id[fa[-val[i]]]].pb (i);
}
ott (i, 1, idx) {
if (val[i] > 0) break;
OTH = 0; for (int v : e[-val[i]]) {
if (id[v]) continue;
if (!OTH) {
val[OTH = id[v] = ++ idx] = v;
E[FA[OTH] = i].pb (OTH);
}
push (v, OTH);
}
}
ott (i, 1, idx) if (val[i] > 0) b[i].init ();
ott (i, 1, m) {
int x = a[i].x; char c = a[i].c;
if (ch[x] != 'C') cup (id[x], -1); if (ch[x] != 'A') cdn (FA[id[x]], -1);
if (ch[x] == 'A') res -= 1ll * dn[x];
if (ch[x] == '?') res -= 1ll * max (0, dn[x] - up[x]);
ch[x] = c;
if (ch[x] == 'A') res += 1ll * dn[x];
if (ch[x] == '?') res += 1ll * max (0, dn[x] - up[x]);
if (ch[x] != 'C') cup (id[x], 1); if (ch[x] != 'A') cdn (FA[id[x]], 1);
printf ("%lld\n", res);
}
ott (i, 1, idx) {
E[i].clear (), FA[i] = 0;
if (val[i] < 0) val[i] = -val[i];
else b[i].clear ();
id[val[i]] = 0, val[i] = 0;
}
m = idx = 0, res = 0; red (1);
return ;
}
int main () {
//freopen ("data.in", "r", stdin);
//freopen ("res.out", "w", stdout);
n = read (), q = read (), scanf ("%s", ch + 1); ott (i, 2, n) e[fa[i] = read ()].pb (i);
B = 1000; dfs0 (1);
ott (j, 1, 19) {
ott (i, 1, idx - (1 << j) + 1) {
int f1 = f[i][j - 1], f2 = f[i + (1 << j - 1)][j - 1];
f[i][j] = dep[f1] < dep[f2] ? f1 : f2;
}
}
lg[0] = -1; ott (i, 1, idx) lg[i] = lg[i >> 1] + 1;
idx = 0, red (1); ott (i, 1, q) {
int x = read (); char c = getchar ();
a[++ m] = {x, c};
if (i % B == 0 || i == q) sol ();
}
return 0;
}