테페리넷

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

===== 풀이 =====
  * 트리 DP 문제
  * 어떤 서브트리의 DP값을, 자신의 parent에서 모든 리프노드를 끊는데 필요한 최소 비용이라고 하면, 이 값은 min({자신과 parent사이의 엣지를 끊는 비용}, {자신과 모든 차일드들간의 엣지를 끊는 비용}) 으로 구할 수 있다.
  * 총 시간복잡도는 O(n)
  * 노드 1개로 이루어진 트리가 문제로 주어지는 경우도 있으니 처리에 주의.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12784. 인하니카 공화국".

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

Tags: [DP] [DP on Tree]
"""

import sys
from teflib import ttree

ROOT = 0


def calc_dp(subtree_vals, _, weight_to_par):
    if weight_to_par and subtree_vals:
        return min(weight_to_par, sum(subtree_vals))
    if weight_to_par:
        return weight_to_par
    return sum(subtree_vals)


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M = [int(x) for x in sys.stdin.readline().split()]
        wtree = [[] for _ in range(N)]
        for _ in range(M):
            u, v, D = [int(x) for x in sys.stdin.readline().split()]
            wtree[v - 1].append((u - 1, D))
            wtree[u - 1].append((v - 1, D))

        print(ttree.dp_on_weighted_tree(wtree, calc_dp, ROOT))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:ttree#dp_on_weighted_tree|teflib.ttree.dp_on_weighted_tree]]

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