UOJ Logo

NOI.AC

1S 512MB

#62. color

Statistics

color

题目描述

给出一棵 $n$ 个节点的有根树,每个叶子有一个或黑或白的颜色,而对于非叶子节点的颜色按以下规则定义,如果它的所有儿子节点的颜色全部相同,则为它儿子的颜色,否则为灰色。

现在有 $m$ 次操作,每次操作会修改一个叶子节点的颜色(由白变黑或由黑变白),每次操作后对应的非叶子节点的颜色也会发生改变。求每次操作后黑白灰三种颜色的节点个数。

输入格式

第一行两个整数 $n, m$ ,表示树的节点个数和操作次数。

第二行一共 $n$ 个整数, $p_i$ 表示编号为 $i$ 的节点的父亲节点编号,若 $p_i=0$ 则该节点为整棵树的根。

第三行一个 $n$ 个整数, $c_i$ 表示编号为 $i$ 的节点的初始颜色(1表示黑色,0表示白色),非叶子节点信息无意义。

接下来一共 $m$ 行,每行一个数,表示修改颜色的节点的编号,保证该节点一定为叶子节点。

输出格式

一共 $m$ 行,每行三个整数,分别表示黑色,白色和灰色节点的个数。

样例

输入

7 5
0 1 1 2 2 2 3
0 1 0 1 1 1 0
4
6
7
5
6

输出

2 3 2
1 4 2
3 2 2
2 4 1
3 2 2

数据范围

$n,m \leq 100000, p_i < i$,只有一个$p_i=0$。

Subtask1 ($30\%$) : $n,m \leq 1000$ 。

Subtask2 ($70\%$) :无特殊限制。

时间限制: $1s$ 。

空间限制: $256MB$ 。