한양 체리 피킹 대회
시간 제한1초메모리 제한1024 MB
두 사람이 트리의 정점을 번갈아 가져가는 게임에서 최적으로 두면 누가 이기는지 구합니다.
문제
세훈이와 철민이는 제10회 HCPC (Hanyang Cherry Picking Contest)에 참가했다. 결승전에서 만난 둘은 우승을 두고 대결한다. HCPC의 규칙은 다음과 같다.
- 정점 개로 이루어진 트리가 주어진다. 트리의 루트는 번 정점이다. 각 정점에는 이상 이하의 정수가 적혀 있다.
- 각 시합은 두 플레이어가 겨룬다. 한 명이 선공, 다른 한 명이 후공이 된다.
- 플레이어는 정점을 가져감으로써 그 정점의 점수를 얻는다. 정점의 점수는 그 정점에 적힌 수이다.
- 직전 턴의 플레이어가 마지막으로 가져간 정점을 체리 정점이라고 한다.
- 첫 번째 턴에 선공 플레이어는 반드시 루트를 가져가고 턴을 후공 플레이어에게 넘긴다. 따라서 체리 정점의 초깃값은 루트이다.
- 그 뒤로 두 플레이어가 번갈아 가며, 턴을 맡은 플레이어는 체리 정점의 자식 정점 중 하나를 골라 가져간 뒤 턴을 넘긴다.
- 어느 한 플레이어가 이미 가져간 정점은 두 플레이어 모두 다시 가져갈 수 없다.
- 체리 정점의 자식이 하나뿐이라면 그 자식을 가져가야 한다.
- 체리 정점에 자식이 없다면, 가져갈 수 있는 자식이 남아 있는 가장 가까운 정점을 체리 정점으로 삼고 턴을 진행한다.
- 가져갈 수 있는 정점이 더 이상 없을 때까지 시합을 진행한다. 시합이 끝난 뒤 가져간 정점들의 점수 합이 더 높은 플레이어가 승리한다. 점수가 같으면 무승부이다.
세훈이가 선공이고 철민이가 후공이다. 두 플레이어가 모두 최적의 전략으로 플레이할 때 HCPC의 우승자는 누구인가?
입력
첫 번째 줄에 이 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 트리의 간선을 나타내는 두 정수 , 가 공백으로 구분되어 주어진다. 이는 번 정점과 번 정점을 잇는 양방향 간선이 있다는 뜻이다.
번째 줄에 개의 정수 이 주어진다. 는 번 정점에 적힌 수이다.
출력
첫 번째 줄에 세훈이가 승리하면 Sehun, 철민이가 승리하면 Cheolmin, 무승부이면 Draw를 출력한다.