뉴스 전하기

• 트리 DP문제.
• 어떤 노드에서 차일드들에게 뉴스를 전달할때, 전달시간이 오래걸리는 서브트리에 먼저 전달하는 것이 가장 효율적인 방법이다.
• 서브트리에 대한 DP값을, 서브트리의 루트에서 모든 노드로 뉴스를 전달하는 최소 시간으로 정의한다면, DP[0] > DP[1] > DP[2] > .. 으로 정렬되어있을때 DP[root] = max(i + DP[i])가 된다.
• DP값을 한번 갱신할때마다, 정렬을 포함해서 O(|child| * log|child|)가 걸리므로, 총 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 1135. 뉴스 전하기".

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

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

from teflib import ttree

ROOT = 0


def calc_dp(subtree_vals, _):
    subtree_vals.sort(reverse=True)
    return max((t1 + t2 for t1, t2 in enumerate(subtree_vals, 1)), default=0)


def main():
    N = int(input())
    parents = [int(x) for x in input().split()]
    tree = [[] for _ in range(N)]
    for u, par in enumerate(parents):
        if par != -1:
            tree[u].append(par)
            tree[par].append(u)

    print(ttree.dp_on_tree(tree, calc_dp, ROOT))


if __name__ == '__main__':
    main()

• Dependency: teflib.ttree.dp_on_tree