题目背景

2024 年 6 月 GESP C++ 七级编程第 1 题

题目描述

小杨有一棵包含 $n$ 个节点的树，每个节点为白色或黑色。小杨认为一棵树是美丽树，当且仅当删除所有白色节点后，剩余黑色节点仍然连通（组成一棵树）。

每次操作可以选择一个白色节点并将其变为黑色。求最少需要多少次操作，才能使这棵树成为美丽树。

输入格式

第一行输入正整数 $n$。 第二行输入 $n$ 个整数 $a_1,a_2,ldots,a_n$，$a_i=0$ 表示节点 $i$ 为白色，$a_i=1$ 表示节点 $i$ 为黑色。 接下来 $n-1$ 行，每行输入两个正整数 $x_i,y_i$，表示树上的一条边。

输出格式

输出一行一个整数，表示最少操作次数。

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

2

数据范围与提示

• $1 \le n\le 10^5$，$0 \le a_i \le 1$。
• 子任务包括链形树、$n \le 100$ 等情况。
• 样例中将节点 $1$ 和 $3$ 变为黑色后，黑色节点连通。

来源

GESP 2024 年 06 月 C++ 七级 T1