题目描述
给定一棵 $n$ 个结点的有根树，根结点是 1 号。每个点有一个权值 $a_i\in\{0,1,?\}$，问号可以替换成 0 和 1 中的任意一个值。还有 $q$ 次修改操作，每次修改会使得某个点的 $a$ 发生改变。
如果两个点 $i,j$ 满足 $i$ 是 $j$ 的祖先且 $a_i
输入格式
第一行输入 $n,q$。
第二行输入长度为 $n$ 的字符串 $s$，$s_i$ 表示 $a_i$ 的取值。保证 $s_i\in\{0,1,?\}$。
第三行输入 $n-1$ 个数 $fa_{2\cdots n}$ 表示每个点的父亲。
接下来 $q$ 行，每行输入一个正整数 $u$ 和字符 $c$，表示将 $a_u$ 改成 $c$，保证 $c\in\{0,1,?\}$。
输出格式
共 $q$ 行，表示每次修改后的最大的贡献和。
样例输出输出
- 样例输入 1
5 9
0?1?1
1 2 3 3
5 0
1 0
2 0
2 ?
1 1
4 0
1 1
5 0
4 ?- 样例输出 1
4
4
4
4
2
1
1
1
2- 样例输入 2
10 9
0001?0?101
1 2 3 4 1 1 4 5 6
2 ?
8 ?
9 0
4 0
3 ?
10 ?
1 ?
2 1
2 1- 样例输出 2
12
12
12
11
11
11
11
10
10该题还附加了 6 个额外样例，分别对应每个子任务的限制情况。
数据范围
对于 100% 的数据，$1\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$1\le fa_i
子任务编号 分值 $n\le$ $q\le$ 特殊性质 1 10 $10$ $10$ 无 2 10 $2\times 10^5$ $2\times 10^5$ $fa_i=1$ 3 15 $2\times 10^5$ $2\times 10^5$ 任何时刻没有问号 4 15 $10^3$ $10^3$ 无 5 25 $2\times 10^5$ $2\times 10^5$ $fa_i=i-1$ 6 25 $2\times 10^5$ $2\times 10^5$ 无