该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵 $n$ 个点的以 1 号点为根的有根树，每个点都有一个权值($0$或者$1$)，给出初始每个点的权值。

有 $m$ 个操作，读入 $x$，操作有两种形式：

1. 将以 $x$ 为根的子树内的每个点的权值都取反。
2. 询问以 $x$ 为根的子树内有多少个点的权值是 1。

输入格式

第一行两个数 $n, m$。

接下来一行一个长度为 $n$ 的 $01$ 串，表示每个点的初始状态。

接下来 $n - 1$ 行每行两个数 $u, v$，表示一条树边。

接下来 $m$ 行，每行两个整数 $op, x$。若 $op = 0$，则表示本次操作是取反操作；若 $op = 1$ 则表示本次操作是询问操作。

输出格式

对于每一个询问操作输出一行表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
4

说明/提示

共 10 个测试点。

测试点 1, 2, 3 满足 $n, m \leq 10^3$。

测试点 4, 5 满足树的形态是一条链。

对于所有数据满足 $n, m \leq 10^5$。