연습문제
[한양대 HCPC 2023] Hanyang Cherry Picking Contest
- 난이도
- Lv. 5
- 제출
- 2 명
- 참가자
- 2 명
- 정답률
- 100.00 %
- 지원 언어
-
CC++JavaPythonJavaScript
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
C++ | 1초 | 1024MB |
JavaScript | 5초 | 1024MB |
C | 1초 | 1024MB |
Java | 3초 | 1024MB |
Python | 5초 | 1024MB |
세훈이와 철민이는 제10회 HCPC (Hanyang Cherry Picking Contest)에 참가했다. 대회의 결승전에서 만난 둘은 우승을 두고 대결한다. HCPC의 규칙은 다음과 같다.
1. 정점 N개로 이루어진 1번 정점을 루트로 하는 트리가 주어진다. 각 정점에는 0 이상 1010 이하의 정수가 적혀있다.
2. 각 시합은 두 플레이어 사이에서 이루어진다. 한 명이 선공, 다른 한 명은 후공 플레이어가 된다.
3. 플레이어는 정점을 가져감으로써 그 정점의 점수를 얻는다. 정점의 점수는 그 정점에 적힌 수이다.
4. 현재 턴의 전 턴 플레이어가 마지막으로 가져간 정점을 체리 정점이라고 한다.
5. 첫 번째 턴에 선공 플레이어는 무조건 루트를 가져가고 턴을 후공 플레이어에게 넘긴다. 이로써 체리 정점의 초깃값은 루트가 된다.
6. 그 후 번갈아 가며 각 턴 플레이어는 체리 정점의 자식 정점 중 하나를 선택하여 가져간 후 턴을 넘긴다.
7. 어떤 플레이어가 이미 가져간 정점은 두 플레이어 모두 다시 가져갈 수 없다.
8. 만약에 체리 정점에 자식이 하나만 존재한다면 그 자식을 가져가야 한다.
9. 체리 정점에 자식이 존재하지 않는다면 가져갈 수 있는 자식이 남은 가장 가까운 정점을 체리 정점으로 취급하여 턴을 진행한다.
10. 시합은 가져갈 수 있는 정점이 더 이상 남지 않을 때까지 진행한다. 시합이 끝난 후 가져간 정점들의 점수의 합이 더 높은 플레이어가 승리한다. 점수가 같다면 무승부다.
세훈이가 선공이고 철민이가 후공이다. 두 명 모두 최적의 전략으로 플레이할 때 HCPC의 우승자는 과연 누구일까?
제약조건
2 ≤ N ≤ 200 000
0 ≤ ai ≤ 1010
입력형식
첫 번째 줄에 N이 주어진다.
두 번째 줄부터 N-1개의 줄에 걸쳐 트리의 간선을 나타내는 두 정수 u, v가 공백으로 구분되어 주어진다. 이는 u번 정점과 v번 정점을 이어주는 양방향 간선이 존재한다는 의미이다. (1 ≤ u,v ≤ N; u ≠ v)
N+1번째 줄에 N개의 정수 a1,a2, … ,aN이 주어진다. ai는 i번째 정점에 적힌 수이다.
출력형식
첫 번째 줄에 세훈이가 승리한다면 Sehun
을, 철민이가 승리한다면 Cheolmin
을, 무승부라면 Draw
를 출력한다.
입력예제1
7 1 2 1 7 2 4 3 4 4 5 4 6 2 0 2 3 1 2 3
출력예제1
Cheolmin
입력예제2
5 1 2 2 3 3 4 1 5 5 4 3 2 1
출력예제2
Sehun
입력예제3
5 1 2 2 3 3 4 1 5 1 3 1 7 1
출력예제3
Cheolmin