题目描述

给定你一棵根节点为 $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$ 行，每行两个整数，表示一条边连接的两个节点。

输出格式

一个整数，表示最少的操作次数。

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

3

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

3

提示

【数据范围】

对于全部数据，保证：$1 \le n \le 2\times 10^5$， $0\le \mathrm{color}_i\le 1$。