인하니카 공화국

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

"""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()

• Dependency: teflib.ttree.dp_on_weighted_tree