문제
N개의 정점이 N - 1개의 양방향 간선으로 이어진 트리 형태를 이루고 있다.
각 정점에는 1부터 K까지의 색 중 하나로 색칠되어 있다.
j번 정점의 색은 Cj이다.
준혁이는 다음과 같은 작업을 할 수 있다:
- 어떤 색 C와 D를 골라, 색 C가 칠해진 모든 정점의 색을 색 D로 바꾼다.
준혁이는 다음을 만족하는 색 X가 하나 이상 존재하도록 하고 싶다:
- 색 X가 칠해진 정점이 하나 이상 존재한다.
- 색 X가 칠해진 정점들 간에는 색 X로 색칠된 정점들만으로 이루어진 경로를 통해 이동할 수 있다.
위의 조건을 만족하도록 준혁이가 작업을 최소 몇 회 해야 하는지 구하여라.
입력
1번 줄 : N K
2번 ~ N번 줄 : Ai Bi
N + 1번 줄 ~ N + C번 줄 : Cj
- 1 ≤ K ≤ N ≤ 200 000
- Ai, Bi는 i번 간선이 잇는 정점들의 번호
- 1 ≤ Ai, Bi ≤ N
- 1 ≤ Cj ≤ K
출력
첫 번째 줄에 준혁이가 해야 하는 작업의 최소 횟수를 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 점 | N ≤ 20 |
| #2 | 점 | N ≤ 2000 |
| #3 | 점 | 모든 정점은 최대 두 개의 간선이 이어져 있다. |
| #4 | 점 | 문제의 조건 외에 주어진 제한이 없다. |
예제 #1
6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
1
3번 색으로 칠해진 정점들을 모두 1번 색으로 바꾸어주면 1번 색이 조건을 만족한다.
예제 #2
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
2
힌트
출처
JOISC 2020 Day 4
로그인해야 코드를 작성할 수 있어요.