테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 차원의 나무 여행 ======

===== 풀이 =====
  * 풀이는 [[https://upload.acmicpc.net/d5199538-4a09-4211-96ad-5b1d15cc6274|공식 풀이]] 참고. 증명만 떠올리면 코드는 간단하다.
  * 주어진 트리가 star graph인 경우만 제외하면, 모든 이동을 워프로 할수 있으므로 N을 출력. star graph라면 한번은 워프를 못하고 간선을 따라 이동해야 하므로, N-1을 출력.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32755. 차원의 나무 여행".

- Problem link: https://www.acmicpc.net/problem/32755
- Solution link: http://www.teferi.net/ps/problems/boj/32755

Tags: [tree]
"""

from teflib import tree as ttree


def main():
    N, tree = ttree.create_tree_from_input()
    is_star_graph = max(len(neighbors) for neighbors in tree) == N - 1
    print(N - 1 if is_star_graph else N)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}