F-树_牛客练习赛116

树

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一棵以 $1$ 为根且包含 $n$ 个节点的树，每个节点都有初始颜色 $col_i$ 。 $col_i=1$ 表示黑色， $col_i=0$ 表示白色。

如果这棵树的任意节点 $u$ 都满足：在以 $u$ 为根的子树中（包含 $u$ ），黑色节点数量不少于白色节点数量，这棵树就是符合要求的。更正式得说，对于以 $u$ 为根的子树（包含 $u$ ），设 $B_u$ 为黑色节点数量， $W_u$ 为白色节点数量。如果 ${\forall}u\in[1,n]$ ，都有 $W_u\leq B_u$ ，那么这棵树就是符合要求的。

现在有一种补全操作：选择任意一个节点 $u$ ，然后给 $u$ 添加一个儿子节点 $new$ ，节点 $new$ 染黑或染白。

如果至少需要执行 $res$ 次补全操作，才能使这棵树符合要求，那么称这棵树的满意度为 $res$ 。

现在有 $q$ 次修改，每次修改用二元组 $(x,y)$ 表示，意思是将节点 $x$ 修改成颜色 $y$ ，如果 $y=0$ 表示白色， $y=1$ 表示黑色。在每次修改结束后，输出这棵树的满意度。

需要注意的是，修改操作不是独立的，也就是说，第 $i+1$ 次修改操作是在第 $i$ 次修改操作后的树上进行的。

输入描述:

第一行包含两个整数 $n\ q\ (1\le n,q\le2\times10^5)$ ，分别表示树节点个数和修改次数。

第二行包含 $n$ 个整数 $col_i\ (0\le col_i\le 1)$ ，分别表示 $n$ 个节点的颜色， $0$ 表示白色， $1$ 表示黑色。

接下来 $n-1$ 行，每行包含两个整数 $u\ v\ (1\le u,v\le n)$ ，表示一条连接 $u$ 和 $v$ 的树边。

接下来 $q$ 行，每行包含一个二元组 $(x,y),(1\le x\le n,0\le y\le1)$ ，表示将节点 $x$ 修改为颜色 $y$ 。

输出描述:

输出  行，每行包含一个整数，表示第  次操作后的满意度。

示例1

输入

复制

输出

复制

2
0
1

备注:

输入较多，建议使用较快的读入方式，比如scanf。