아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

할리불라에서의 파티

면접 대비

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

요약
회사 조직도가 트리로 주어질 때, 상사와 부하를 동시에 초대하지 않으면서 초대할 수 있는 최대 인원을 구하고, 그 최대 집합이 유일한지 판별한다.
난이도

보통10점 중 6점

유형
트리, 동적 계획법, DFS, 해시맵
정답자
아직 제출이 없습니다

문제

참가자분께,

BCM에서의 은퇴를 기념하기 위해, 할리불라(Hali-Bula)에 있는 제 별장에서 파티를 열려고 합니다. 모든 동료를 초대하고 싶지만, 파티에 왔더니 손님 중에 자기 상사가 있다면 그 직원이 어떻게 파티를 즐길 수 있겠습니까! 그래서 저는 어떤 직원과 그 직원의 상사를 함께 초대하지는 않기로 했습니다.

BCM의 조직도는 트리 구조입니다. 즉, 누구도 두 명 이상의 상사를 두지 않으며, 상사가 전혀 없는 직원은 정확히 한 명(가장 높은 상사, Big Boss)뿐입니다. 초대된 어떤 직원의 상사도 함께 초대되지 않도록 하면서, 초대할 수 있는 손님 수를 최대로 하는 프로그램을 작성해 주시겠습니까? BCM의 직원 명단과 조직도를 첨부합니다.

감사합니다.
-Brian Bennett

추신: 이 조건에서 손님 수를 최대로 하여 초대할 때, 초대되는 사람들의 명단이 유일하게 결정되는지도 프로그램이 함께 알려줄 수 있다면 정말 감사하겠습니다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 각 테스트 케이스는 BCM 직원 수를 나타내는 정수 nn (1≤n≤2001 \le n \le 200)이 적힌 줄로 시작합니다. 다음 줄에는 가장 높은 상사(Big Boss)의 이름만 주어집니다. 이어지는 n−1n - 1개의 줄에는 각각 한 직원의 이름과 그 직원의 상사 이름이 공백으로 구분되어 주어집니다. 모든 이름은 1자 이상 100자 이하의 알파벳 문자열입니다. 입력의 끝은 00 하나만 있는 줄로 표시됩니다.

출력

각 테스트 케이스마다, 주어진 조건에 따라 초대할 수 있는 손님의 최대 수와, 그 최댓값을 달성하는 손님 명단이 유일한지에 따라 Yes 또는 No를 한 줄에 출력합니다.

예제3

  1. 예제 1

    입력
    6
    Jason
    Jack Jason
    Joe Jack
    Jill Jason
    John Jack
    Jim Jill
    2
    Ming
    Cho Ming
    0
    
    예상 출력
    4 Yes
    1 No
    
  2. 예제 2

    입력
    1
    Alice
    0
    
    예상 출력
    1 Yes
    
  3. 예제 3

    입력
    3
    Ada
    Ben Ada
    Cal Ben
    0
    
    예상 출력
    2 Yes