17678번 - 합병 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 246 | 57 | 51 | 25.000% |
문제
JOI합중국에는 $N$개의 도시가 있어서, 1번부터 $N$번까지의 번호가 붙어있다. 또한, JOI합중국에는 $N-1$개의 국도가 있다. $i$ 번째($1 \le i \le N-1$) 국도는 $A_i$번 도시와 $B_i$번 도시를 양방향으로 잇는다. 어떤 두 도시에 대해서도, 국도 몇개를 이용하면 서로 오가는 것이 가능하다.
현재, JOI합중국은 1번부터 $K$번까지의 번호가 붙어있는 $K$개의 주로 나뉘어 있다. $j$번 ($1 \le j \le N$)도시는 $S_j$번 주에 속한다. 모든 주에는 적어도 하나의 도시가 속해 있다.
JOI합중국의 대통령인 $K$이사장은, 이 나라가 분열하지 않을까 걱정이 되었다. 다음 조건을 모두 만족하도록 모든 도시를 2개의 그룹 $X$, $Y$로 나누는 것이 가능할 때, JOI합중국은 분열가능한 상태라고 말한다.
- 모든 도시는 그룹 $X$혹은 그룹 $Y$에 속한다.
- 그룹 $X$에는 적어도 하나의 도시가 속해 있다.
- 그룹 $Y$에는 적어도 하나의 도시가 속해 있다.
- 모든 주에 대해서, 그 주에 있는 모든 도시는 모두 같은 그룹에 속해 있다.
- 그룹 $X$에 속한 어떤 두 도시에 대해서도, 그룹 $X$에 속한 도시만을 경유해서 서로 오가는 것이 가능하다.
- 그룹 $Y$에 속한 어떤 두 도시에 대해서도, 그룹 $Y$에 속한 도시만을 경유해서 서로 오가는 것이 가능하다.
$K$이사장은, JOI합중국이 분열가능하지 않은 상태를 만들기 위해, 주를 합병하려고 한다. 한번의 합병은 두개의 주를 골라서 합치는 것을 말한다. 새로운 주는, 기존의 두 주에 속해 있던 도시 들이 속해있다. K이사장은 주를 최소한의 횟수만큼 합병하여 JOI합중국을 분열가능하지 않은 상태로 만들고 싶어한다.
도시와 국도의 위치, 현재 어떤 도시가 어떤 주에 속해있는가에 대한 상태가 주어졌을 때, JOI 합중국이 분열가능하지 않은 상태로 만들기 위한 합병의 최소 횟수를 구하는 프로그램을 작성하여라.
입력
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_{N-1}$ $B_{N-1}$
$S_1$
$\vdots$
$S_N$
출력
JOI합중국을 분열가능하지 않은 상태로 만들기 위한 합병의 최소횟수를 표준 출력의 첫째 줄에 출력하여라.
제한
- $1 \le N \le 500\ 000$.
- $1 \le K \le N$.
- $1 \le A_i \le N$ ($1 \le i \le N-1$).
- $1 \le B_i \le N$ ($1 \le i \le N-1$).
- 어떤 두 도시에 대해서도, 국도 몇개를 이용하면 서로 오가는 것이 가능하다.
- $1 \le S_j \le K$ ($1 \le j \le N$)
- 모든 $k$ ($1 \le k \le N$)에 대해, $S_j = k$를 만족하는 $j$ ($1 \le j \le N$)가 존재한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | N ≤ 100, K ≤ 7. |
| 2 | 24 | N ≤ 3 000. |
| 3 | 14 | N ≤ 100 000, K ≤ 50. |
| 4 | 22 | N ≤ 100 000. At the initial situation, one can travel between any two cities belonging to the same state by using at most 100 highways. |
| 5 | 30 | No additional constraints. |
예제 입력 1
5 4 1 2 2 3 3 4 3 5 1 2 1 3 4
예제 출력 1
1
이 예제에서는, 처음의 상태는 분열가능하다. 예를 들면, 1번, 2번, 3번, 4번 도시를 그룹 $X$라 하고, 5번 도시를 그룹 $Y$라고 하면 된다.
3번 주와 4번 주를 합병할 경우 분열가능하지 않은 상태가 된다. 그러므로 답은 1이다.
예제 입력 2
5 4 1 2 2 3 3 4 4 5 1 2 3 4 1
예제 출력 2
0
이 예제에서는, 처음의 상태는 분열가능하지 않다. 그러므로 답은 0이다.
예제 입력 3
2 2 1 2 1 2
예제 출력 3
1
출처
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 4-2번
- 문제를 번역한 사람: ho94949
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호