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]
"""

from teflib import psutils
from teflib import wtree as twtree


@psutils.gcj_style
def main():
    _, wtree = twtree.create_wtree_from_input()

    answer = (
        sum(w for u, v, w in twtree.edge_iter(wtree)) * 2
        - twtree.DistanceMeasures(wtree).diameter
    )
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.wtree.DistanceMeasures