#2204. [GESP202406 七级] 黑白翻转

[GESP202406 七级] 黑白翻转

Description

小杨有一棵包含 nn 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且 仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变 为美丽树。

Input Format

第一行包含一个正整数 nn ,代表树的节点数。

第二行包含 nn 个非负整数 a1,a2,...,ana_1,a_2,...,a_n ,其中如果 ai=0a_i=0 ,则节点 ii 的颜色为白色,否则为黑色。

之后 n1n-1 行,每行包含两个正整数 xi,yix_i,y_i ,代表存在一条连接节点 xix_iyiy_i 的边。

Output Format

输出一个整数,代表最少执行的操作次数。

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

2

Hint

样例解释

将节点 1133 变为黑色即可使这棵树变为美丽树,此时删除白色节点 55 ,剩余黑色节点仍然组成一棵树。

数据范围

子任务编号 数据点占比 nn aia_i 特殊条件
1 20%20\% 105\leq 10^5 0ai10\leq a_i \leq 1 树的形态为一条链
2 40%40\% 100\leq 100 只有两个节点颜色为黑色
3 40% 40\% 105\leq 10^5

对于全部数据,保证有 1n105,0ai11 \leq n \leq 10^5 , 0 \leq a_i \leq 1

Source

GESP七级202406