30872번 - Hanyang Cherry Picking Contest 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 152 | 50 | 45 | 43.689% |
문제
세훈이와 철민이는 제10회 HCPC (Hanyang Cherry Picking Contest)에 참가했다. 대회의 결승전에서 만난 둘은 우승을 두고 대결한다. HCPC의 규칙은 다음과 같다.
- 정점 $N$개로 이루어진 $1$번 정점을 루트로 하는 트리가 주어진다. 각 정점에는 $0$ 이상 $10^{10}$ 이하의 정수가 적혀있다.
- 각 시합은 두 플레이어 사이에서 이루어진다. 한 명이 선공, 다른 한 명은 후공 플레이어가 된다.
- 플레이어는 정점을 가져감으로써 그 정점의 점수를 얻는다. 정점의 점수는 그 정점에 적힌 수이다.
- 현재 턴의 전 턴 플레이어가 마지막으로 가져간 정점을 체리 정점이라고 한다.
- 첫 번째 턴에 선공 플레이어는 무조건 루트를 가져가고 턴을 후공 플레이어에게 넘긴다. 이로써 체리 정점의 초깃값은 루트가 된다.
- 그 후 번갈아 가며 각 턴 플레이어는 체리 정점의 자식 정점 중 하나를 선택하여 가져간 후 턴을 넘긴다.
- 어떤 플레이어가 이미 가져간 정점은 두 플레이어 모두 다시 가져갈 수 없다.
- 만약에 체리 정점에 자식이 하나만 존재한다면 그 자식을 가져가야 한다.
- 체리 정점에 자식이 존재하지 않는다면 가져갈 수 있는 자식이 남은 가장 가까운 정점을 체리 정점으로 취급하여 턴을 진행한다.
- 시합은 가져갈 수 있는 정점이 더 이상 남지 않을 때까지 진행한다. 시합이 끝난 후 가져간 정점들의 점수의 합이 더 높은 플레이어가 승리한다. 점수가 같다면 무승부다.
세훈이가 선공이고 철민이가 후공이다. 두 명 모두 최적의 전략으로 플레이할 때 HCPC의 우승자는 과연 누구일까?
입력
첫 번째 줄에 $N$이 주어진다. $(2\le N\le 200\, 000)$
두 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선을 나타내는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 이어주는 양방향 간선이 존재한다는 의미이다. $(1\le u,v\le N;$ $u\ne v)$
$N+1$번째 줄에 $N$개의 정수 $a_1,a_2,\ldots ,a_N$이 주어진다. $a_i$는 $i$번째 정점에 적힌 수이다. $(0\le a_i\le 10^{10})$
출력
첫 번째 줄에 세훈이가 승리한다면 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
출처
University > 한양대학교 > 제10회 한양대학교 프로그래밍 경시대회(HCPC) > Beginner Division E번
- 문제를 만든 사람: hibye1217, seonah
- 문제를 검수한 사람: andrewmjk1, mjhmjh1104, mnx, solvedac, yijw0930
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호