페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2614

[고등부] 2025 KOI 1차대회 대비 파이널 모의고사

도로 재건
서브태스크
1초 1024MB

문제

비버국에는 N개의 도시와 도시를 잇는 N-1개의 도로가 있다.

현재 모든 도시는 도로를 통해 서로 도달할 수 있는 상태이다.


N-1개의 모든 도로는 다음과 같은 재건을 해야한다.

i번 도시와 j번 도시를 잇는 도로에 대해 다음 4가지 종류의 도로 중 하나로 재건한다.

  1. 양방향 도로: i번 도시에서 j번 도시로 갈 수 있다. j번 도시에서 i번 도시로 갈 수 있다.

  2. 단방향 도로: i번 도시에서 j번 도시로만 갈 수 있다.

  3. 단방향 도로: j번 도시에서 i번 도시로만 갈 수 있다.

  4. 폐쇄된 도로: i번 도시와 j번 도시는 서로 갈 수 없다.

안타깝게도 비버국의 국토교통부가 비리로 해체되어 재건 계획 문서가 사라졌다.

이에, 비버국의 대통령 비브라스는 유능한 당신에게 복구를 요청하였다.

아무 정보 없이 복구를 할 수는 없기에, 비브라스에게 아래와 같은 추가적인 정보를 요구하였다.

"재건을 했다면, 각 도시에서 출발하여 도달할 수 있는 도시의 수는 몇 개입니까?"

따라서 비브라스는 각 도시의 비버에게 값을 얻어내어 당신에게 알려주었다.

하지만 비리로 물든 비버들이 알려준 값은 확신할 수 없다. 따라서 이 값들이 맞는지 검증을 해야한다!

여기서 "도달할 수 있는" 이라는 정의는, c_1에서 c_k로 도달할 수 있는 상황이라면, c_1도시에서 c_k도시의 경로를 c_1-c_2-...-c_k 라고 했을 때,

1\le x \le k-1 조건 하에, c_x 도시에서 c_{x+1}도시로 갈 수 있음을 의미한다.

또한, 자신의 도시도 도달할 수 있다.


입력

첫 줄에 도시의 수 N이 주어진다. ( 1 \le N \le 5\,000 )

다음 줄에 각 도시의 비버들이 알려준 N개의 N이하의 자연수 값이 공백을 구분으로 주어진다.

이어지는 다음 N-1개의 줄에 걸쳐 N-1개의 도로 정보가 주어진다.

도로 정보는 N이하의 두 자연수가 공백을 구분으로 주어진다. 이는 두 도시가 연결되어 있다는 의미이다.

"모든 도시는 도로를 통해 서로 도달할 수 있는 상태로 주어진다."


출력

적절하게 도로 재건을 해서 비버들이 알려준 값으로 만들 수 있으면 "YES", 없으면 "NO"를 출력한다.


부분문제

번호 점수 조건
#11점

입력 예제

#24점

N \le 7

#35점

N \le 15

#411점

각 도시에서 도달할 수 있는 도시의 수가 모두 같다.

#510점

답이 "YES"라면, 양방향 도로 없이 구성할 수 있는 방법이 존재한다.

#644점

N \le 400

#725점

추가 제약 조건 없음.


예제 #1

9
5 2 3 5 2 3 1 1 1
1 4
4 5
2 5
3 6
5 6
6 9
7 8
4 7
YES

재건 후 도로 상태에서,

1번 도시는 5개의 도시에 도달할 수 있다. (1,4,7,5,2)

2번 도시는 2개의 도시에 도달할 수 있다. (2,5)

3번 도시는 3개의 도시에 도달할 수 있다. (3,6,9)

4번 도시는 5개의 도시에 도달할 수 있다. (1번 도시와 동일)

5번 도시는 2개의 도시에 도달할 수 있다. (2번 도시와 동일)

6번 도시는 3개의 도시에 도달할 수 있다. (3번 도시와 동일)

7번 도시는 1개의 도시에 도달할 수 있다. (7)

8번 도시는 1개의 도시에 도달할 수 있다. (8)

9번 도시는 1개의 도시에 도달할 수 있다. (9)

따라서 비버들이 알려준 값은 올바른 값이다.


예제 #2

9
5 2 3 5 2 3 1 1 2
1 4
4 5
2 5
3 6
5 6
6 9
7 8
4 7
NO

예제 #3

7
3 3 1 3 2 1 2
3 4
1 2
6 2
7 3
5 6
4 2
YES
로그인해야 코드를 작성할 수 있어요.