Interesting Outing

• 시작점과 끝점을 고정해놓고서 투어를 시작한다고 해보자. 최적 경로로 움직이면, u→v 단순경로상의 엣지들은 한번씩, 나머지 엣지들은 두번씩 방문하게 된다는 것을 쉽게 알수 있다. 따라서 전체 비용은 {모든 엣지의 비용}*2-{u→v 경로의 비용} 이 되고, u→v 경로의 비용을 가장 크게 하는 u,v를 잡을때 최소 비용을 얻을수 있다. 이것은 결국 트리의 지름을 구하라는 것과 동일하다.
• 트리의 지름은 O(n)에 구할수 있으므로, 전체 시간복잡도도 O(n)이다

"""Solution code for "BOJ 24921. Interesting Outing".

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

Tags: [diameter of tree]
"""

import sys
from teflib import tree as ttree

INF = float('inf')


def main():
    T = int(sys.stdin.readline())
    for case_no in range(1, T + 1):
        N = int(sys.stdin.readline())
        wtree = ttree.create_wtree_from_input(N)

        answer = sum(
            sum(wtree_u.values()) for wtree_u in wtree
        ) - ttree.diameter(wtree)
        print(f'Case #{case_no}: {answer}')


if __name__ == '__main__':
    main()