Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1155.

Problem Description

Xiao Yang has a tree with $n$ nodes. Each node in the tree is either white or black. Xiao Yang considers a tree to be a beautiful tree if and only if, after deleting all white nodes, the remaining nodes still form a tree.

In each operation, Xiao Yang can choose one white node and change its color to black. He wants to know the minimum number of operations needed to make the tree become a beautiful tree.

Input Format

The first line contains a positive integer $n$, representing the number of nodes in the tree.

The second line contains $n$ non-negative integers $a_1,a_2,\ldots,a_n$. If $a_i=0$, then node $i$ is white; otherwise, it is black.

Then follow $n-1$ lines. Each line contains two positive integers $x_i,y_i$, indicating that there is an edge connecting node $x_i$ and node $y_i$.

Output Format

Output one integer, representing the minimum number of operations needed.

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

2

Hint

Sample Explanation

Changing nodes $1$ and $3$ to black is enough to make the tree a beautiful tree. At this time, after deleting the white node $5$, the remaining black nodes still form a tree.

Constraints

For all testdata, it is guaranteed that $1\leq n\leq 10^5$ and $0\leq a_i\leq 1$.

Translated by ChatGPT 5