Monochrome Tree
题目描述
给定你一棵根节点为 $1$ 的树,对于任意的节点 $u$ 都只能有两种颜色:黑或白。每个节点 $u$ 的起始颜色都是已知的,记为 $\mathrm{color}_u$。
现在你有两种操作:
- 操作 $1$:把任意一个节点 $u$ 到根节点的路径上节点的颜色全部翻转(路径包括 $u$ 和根节点)。
- 操作 $2$:把任意一个以 $u$ 为根节点的子树上的节点颜色全部翻转($u$ 的子树包括 $u$)。
现在问你,最少需要几次操作才能把整棵树变成黑色。
输入输出格式
输入格式
第一行一个整数 $n$ 表示节点个数。
第二行 $n$ 个整数表示 $\mathrm{color}_i$,$\mathrm{color}_i=0$ 代表 $i$ 节点初始为白色,$\mathrm{color}_i=1$ 代表 $i$ 节点初始为黑色。
接下来 $n-1$ 行,每行两个整数,表示一条边连接的两个节点。
输出格式
一个整数,表示最少的操作次数。
输入输出样例
输入样例 #1
6
0 1 1 1 0 0
1 2
1 3
2 5
5 4
5 6
输出样例 #1
3
输入样例 #2
7
0 0 1 0 0 1 1
6 4
3 4
3 5
1 5
7 3
2 7
输出样例 #2
3
说明
#### 【数据范围】
对于全部数据,保证:$1 \le n \le 2\times 10^5$, $0\le \mathrm{color}_i\le 1$。
|$\text{Subtask}$|$n\leq$|分值|特殊性质|
|:-:|:-:|:-:|:-:|
|$0$|$5$|$3$|无|
|$1$|$10$|$7$|无|
|$2$|$2\times 10^3$|$29$|无|
|$3$|$2\times 10^5$|$61$|无|