BOJ 7812(중앙 트리)풀이

https://www.acmicpc.net/problem/7812

7812번: 중앙 트리

이 문제는 전에 올렸던 사무실 이전과 같은 방식의 문제이다.

https://joseph0528.tistory.com/77

BOJ 16121(사무실 이전)풀이

이 글을 참고하면서 읽는 걸 추천하다.

이 문제도 똑같이 자식들간의 거리합과 부모들 간의 거리합을 따로 구해줄 것이다. 자식들 간의 거리합은 골드 급의 생각이라 간단하게만 설명하겠다.

자식들 간의 거리는 현재 x노드에 대해 x노드의 자식들의 값+간선 값*자식들의 개수를 더해주면 된다. 

이게 끝이다.

이제 부모들간의 거리합을 구해줘야 하는데 이것도 위에서부터 내려오면서 x노드의 자식들 중 x [i] 노드로 탐색을 한다고 했을 때 (x노드의 값에 x [i] 노드의 값과 두 노드를 연결하는 값을 빼준 값)+부모 노드의 값(첫 번째에서 구한 값이 아닌 두 번째에서 구한 값)+(x노드가 포함하는 자식 개수-x [i] 노드가 포함하는 자식 노드 개수)*(두 노드를 이으는 간선 값)를 구해주면 된다.

이제 마지막에 n번 돌면서 합이 가장 작은걸 구해주면 된다.

import sys,math
inf=math.inf
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
def f(x,lt):
    v=0
    cnt=1
    for next in graph[x]:
        if next[0]!=lt:
            rt=f(next[0],x)
            cnt+=rt[1]
            v+=rt[0]+rt[1]*next[1]
    dp[x]=[v,cnt]
    return dp[x]
def ff(x,lt,vc):
    for next in graph[x]:
        if next[0]!=lt:
            #print(dp1[x],dp[x][1],next[1],dp[x][0],dp[next][0])
            dp1[next[0]]=dp1[x]+(dp[x][1]-dp[next[0]][1]+vc)*next[1]+(dp[x][0]-dp[next[0]][0]-dp[next[0]][1]*next[1])
            ff(next[0],x,vc+dp[x][1]-dp[next[0]][1])
while 1:
    a=int(input())
    dp=[0]*(a+1)
    dp1=[0]*(a+1)
    if a==0:break
    graph=[[]for i in range(a+1)]
    for i in range(a-1):
        c,d,e=map(int,input().split())
        graph[c+1].append([d+1,e])
        graph[d+1].append([c+1,e])
    f(1,-1)
    ff(1,-1,0)
    #print(dp)
    #print(dp1)
    mi=inf
    for i in range(1,a+1):
        mi=min(mi,dp[i][0]+dp1[i])
    print(mi)