树

题目描述 给定一棵𝑛𝑛个点的以1号点为根的有根树，每个点都有一个01权值，给出初始每个 点的权值。

有𝑚𝑚个操作，读入𝑥𝑥，操作有两种形式：

1.   将以𝑥𝑥为根的子树内的每个点的权值都取反。

2.   询问以𝑥𝑥为根的子树内有多少个点的权值是1。

输入格式 第一行两个数𝑛𝑛, 𝑚𝑚。

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

接下来𝑛𝑛 − 1行每行两个数𝑢𝑢, 𝑣𝑣，表示一条树边。

接下来𝑚𝑚行，每行两个整数𝑜𝑜𝑜𝑜, 𝑥𝑥。若𝑜𝑜𝑜𝑜 = 0，则表示本次操作是取反操作；若 𝑜𝑜𝑜𝑜 = 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满足𝑛𝑛, 𝑞𝑞 ≤ 103 。 测试点4,5满足树的形态是一条链。

对于所有数据满足𝑛𝑛, 𝑞𝑞 ≤ 105 。