만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

한양 체리 피킹 대회

시간 제한1초메모리 제한1024 MB

요약
두 사람이 트리의 정점을 번갈아 가져가는 게임에서 최적으로 두면 누가 이기는지 구합니다.
난이도

어려움10점 중 8점

유형
트리, 게임 이론, 동적 계획법
정답자
아직 제출이 없습니다

문제

세훈이와 철민이는 제10회 HCPC (Hanyang Cherry Picking Contest)에 참가했다. 결승전에서 만난 둘은 우승을 두고 대결한다. HCPC의 규칙은 다음과 같다.

  1. 정점 NN개로 이루어진 트리가 주어진다. 트리의 루트는 11번 정점이다. 각 정점에는 00 이상 101010^{10} 이하의 정수가 적혀 있다.
  2. 각 시합은 두 플레이어가 겨룬다. 한 명이 선공, 다른 한 명이 후공이 된다.
  3. 플레이어는 정점을 가져감으로써 그 정점의 점수를 얻는다. 정점의 점수는 그 정점에 적힌 수이다.
  4. 직전 턴의 플레이어가 마지막으로 가져간 정점을 체리 정점이라고 한다.
  5. 첫 번째 턴에 선공 플레이어는 반드시 루트를 가져가고 턴을 후공 플레이어에게 넘긴다. 따라서 체리 정점의 초깃값은 루트이다.
  6. 그 뒤로 두 플레이어가 번갈아 가며, 턴을 맡은 플레이어는 체리 정점의 자식 정점 중 하나를 골라 가져간 뒤 턴을 넘긴다.
  7. 어느 한 플레이어가 이미 가져간 정점은 두 플레이어 모두 다시 가져갈 수 없다.
  8. 체리 정점의 자식이 하나뿐이라면 그 자식을 가져가야 한다.
  9. 체리 정점에 자식이 없다면, 가져갈 수 있는 자식이 남아 있는 가장 가까운 정점을 체리 정점으로 삼고 턴을 진행한다.
  10. 가져갈 수 있는 정점이 더 이상 없을 때까지 시합을 진행한다. 시합이 끝난 뒤 가져간 정점들의 점수 합이 더 높은 플레이어가 승리한다. 점수가 같으면 무승부이다.

세훈이가 선공이고 철민이가 후공이다. 두 플레이어가 모두 최적의 전략으로 플레이할 때 HCPC의 우승자는 누구인가?

입력

첫 번째 줄에 NN이 주어진다. (2≤N≤200 000)(2\le N\le 200\,000)

두 번째 줄부터 N−1N-1개의 줄에 걸쳐 트리의 간선을 나타내는 두 정수 uu, vv가 공백으로 구분되어 주어진다. 이는 uu번 정점과 vv번 정점을 잇는 양방향 간선이 있다는 뜻이다. (1≤u,v≤N;(1\le u,v\le N; u≠v)u\ne v)

N+1N+1번째 줄에 NN개의 정수 a1,a2,…,aNa_1,a_2,\ldots,a_N이 주어진다. aia_i는 ii번 정점에 적힌 수이다. (0≤ai≤1010)(0\le a_i\le 10^{10})

출력

첫 번째 줄에 세훈이가 승리하면 Sehun, 철민이가 승리하면 Cheolmin, 무승부이면 Draw를 출력한다.

예제3

  1. 예제 1

    입력
    7
    1 2
    1 7
    2 4
    3 4
    4 5
    4 6
    2 0 2 3 1 2 3
    
    예상 출력
    Cheolmin
    
  2. 예제 2

    입력
    5
    1 2
    2 3
    3 4
    1 5
    5 4 3 2 1
    
    예상 출력
    Sehun
    
  3. 예제 3

    입력
    5
    1 2
    2 3
    3 4
    1 5
    1 3 1 7 1
    
    예상 출력
    Cheolmin