우수 마을

[BOJ 1949] 우수 마을 (Gold II)

1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 위 문제를 풀고 나서 되돌아보며 부족했던 부분을 채우고자 합니다. 저의 풀이와 다른 사람들의 풀이를 보고 느낀 점을 서술합니다. 나의 풀이 처음에 문제를 대충 읽었다가 주어지는 게 그냥 그래프인 줄 알았는데, 간선 입력이 N-1개 주어진다는 걸 보고 문제를 다시 읽어 보니 트리인 걸 알아차렸다. 문제를 보면 일단 어디가 루트 노드인지 알 수 없기 때문에 기본적으로 1번 노드를 루트 노드로 하여금 트리를 형성하고, 트리를 순회하면서 값을 계산하도록 한다...