색칠된 잎

시간 제한1초메모리 제한128 MB

요약

잎의 색이 정해진 무향 트리에서 내부 정점 하나를 루트로 골라, 각 잎의 색이 마지막 표지 색과 같아지도록 필요한 최소 표지 수를 구한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

트리 $T$ 가 주어진다. 리프(leaf, 즉 잎)가 아닌 내부 정점 하나를 골라 루트로 삼는다.

일부 정점에는 "검정" 또는 "흰색" 라벨을 붙일 수 있다(리프와 루트에도 라벨을 붙일 수 있다). 각 리프 $w$ 에 대해, 루트에서 $w$ 까지의 단순 경로 위에는 반드시 라벨이 붙은 정점이 하나 이상 있어야 하며, $w$ 의 색은 그 경로에서 $w$ 에 가장 가까운(즉 마지막) 라벨 정점의 색으로 정해진다.

리프의 색이 모두 정해진, 루트가 지정되지 않은 트리가 주어진다. 트리의 임의의 내부 정점을 루트로 선택할 수 있을 때, 위 방식으로 리프의 색을 정확히 재현하는 데 필요한 라벨의 최소 개수를 구하라.

입력

첫째 줄에 두 정수 $m$ 과 $n$ 이 주어진다 ( $2 \le n < m \le 10000$ ). $m$ 은 $T$ 의 정점 수, $n$ 은 리프의 수이다. 정점에는 $1, 2, \dots, m$ 의 번호가 매겨져 있고, 리프에는 번호 $1, 2, \dots, n$ 이 배정된다.

이어지는 $n$ 개의 줄 중 $i$ 번째 줄에는 $0$ 또는 $1$ 이 주어지며, 이는 리프 $i$ 의 색을 나타낸다( $0$ 은 검정, $1$ 은 흰색).

그다음 $m-1$ 개의 줄에는 각각 공백으로 구분된 두 정수 $a$ , $b$ 가 주어진다 ( $1 \le a < b \le m$ ). 각 줄은 $T$ 의 간선 하나를 나타낸다.

출력

위 방식으로 리프의 색을 정하는 데 필요한 라벨의 최소 개수를 정수 하나로 출력한다.

예제6

예제 1
입력
```
5 3
0
1
0
1 4
2 5
4 5
3 5
```
예상 출력
```
2
```
예제 2
입력
```
3 2
0
0
1 3
2 3
```
예상 출력
```
1
```
예제 3
입력
```
3 2
0
1
1 3
2 3
```
예상 출력
```
2
```
예제 4
입력
```
5 4
1
1
1
1
1 5
2 5
3 5
4 5
```
예상 출력
```
1
```
예제 5
입력
```
5 4
1
0
1
0
1 5
2 5
3 5
4 5
```
예상 출력
```
3
```
예제 6
입력
```
7 4
0
0
1
1
1 5
2 5
3 6
4 6
5 7
6 7
```
예상 출력
```
2
```