Coloured Leaves

Time limit1sMemory limit128 MB

Summary

Given an unrooted tree whose leaves have fixed colors, choose an internal vertex as root and place the fewest labels so each leaf's color matches its last labeled vertex.

Level: Medium7 of 10
Topics: Tree, DFS, Dynamic programming, Greedy
Solved: No attempts yet

Problem

You are given a tree $T$ . Choose one internal vertex (a vertex that is not a leaf) to be the root.

Some vertices may be labelled either "black" or "white" — leaves and the root may be labelled as well. For every leaf $w$ , the simple path from the root to $w$ must contain at least one labelled vertex, and the colour of $w$ is defined by the label of the last labelled vertex on that path (the labelled vertex closest to $w$ ).

You are given an unrooted tree (no root is fixed) whose leaves are already coloured. You may choose any internal vertex of the tree as its root. Find the minimum number of labels needed to reproduce the given leaf colours in the manner described above.

Input

The first line contains two integers $m$ and $n$ ( $2 \le n < m \le 10000$ ), where $m$ is the number of vertices of $T$ and $n$ is the number of leaves. The vertices are numbered $1, 2, \dots, m$ , and the numbers $1, 2, \dots, n$ are assigned to the leaves.

Each of the next $n$ lines contains a single number, $0$ or $1$ , describing the colour of a leaf ( $0$ for black, $1$ for white). The $i$ -th of these lines describes the colour of leaf $i$ .

Each of the following $m-1$ lines contains two integers $a$ and $b$ ( $1 \le a < b \le m$ ) separated by a single space, describing one edge of $T$ .

Output

Print a single integer — the minimum number of labels needed to define the colours of the leaves in the way described in the input.

Examples6

Example 1
Input
```
5 3
0
1
0
1 4
2 5
4 5
3 5
```
Expected output
```
2
```
Example 2
Input
```
3 2
0
0
1 3
2 3
```
Expected output
```
1
```
Example 3
Input
```
3 2
0
1
1 3
2 3
```
Expected output
```
2
```
Example 4
Input
```
5 4
1
1
1
1
1 5
2 5
3 5
4 5
```
Expected output
```
1
```
Example 5
Input
```
5 4
1
0
1
0
1 5
2 5
3 5
4 5
```
Expected output
```
3
```
Example 6
Input
```
7 4
0
0
1
1
1 5
2 5
3 6
4 6
5 7
6 7
```
Expected output
```
2
```