[BOJ 7812] 중앙트리

문제

www.acmicpc.net/problem/7812

7812번: 중앙 트리

 

---

풀이

트리DP를 사용합니다.

먼저, 예제에서 나온 트리를 보겠습니다.

 

위 트리의 \(A\)노드에서 다른 모든 노드들로 이동할 때, 각 간선이 이용되는 횟수는 다음과 같습니다.

 

\(A\)를 루트로 하여 트리를 순회하면서 각 \((B, C, D, E)\)를 루트로 하는 서브 트리의 크기(노드의 개수, 즉, 루트라고 하는 노드와 그 노드의 부모와 이어지는 간선이 이용되는 횟수)에 그 간선의 가중치를 곱한 다음 그들의 합을 구하면 A가 중앙 정점일 때의 합을 구할 수 있습니다.

\((A\)의 경우\(: 2 \cdot 4 + 1 \cdot 1 + 2 \cdot 7 + 5 \cdot 1 = 28)\)

 

모든 노드마다 위의 방법을 이용해서 구하면 시간이 오래 걸릴 수 있기에 더 간단하고 빠른 방법을 사용해보겠습니다.

\(A\)의 자식 노드인 \(B\)를 루트로 할 경우는 다음과 같습니다.

 

그림을 보면 \(A\)와 \(B\)를 이으는 간선 말고는 모두 이용되는 횟수가 같습니다. 즉, 트리를 순회하면서 다음 노드의 가중치의 합을 구할 때는 전 노드의 가중치의 합에서 전 노드와 이어지는 간선의 가중치와 다음 노드의 서브 트리의 크기의 곱을 뺀 다음, 다음 노드의 서브 트리에 포함되지 않는 노드의 개수, 즉, 전체 노드의 개수에서 다음 노드의 서브 트리의 크기를 뺀 값에 간선의 가중치를 곱한 것을 더해주면 다음 노드의 가중치의 합이 됩니다.

\((B\)의 경우\(: 28 - 2 \cdot 4 + 2 \cdot 1 = 22)\)

​

이렇게 구한 값들 중 최솟값이 답이 됩니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int N;
ll mn;
vector<ll> cnt, sum;
vector<vector<p>> graph;

void get_tree(int cur, int pnode) {
    cnt[cur] = 1;

    for (int i = 0; i < graph[cur].size(); ++i) {
        if (graph[cur][i].x == pnode) continue;
        int next = graph[cur][i].x;
        int cost = graph[cur][i].y;
        get_tree(next, cur);
        cnt[cur] += cnt[next];
        sum[cur] += cnt[next] * cost + sum[next];
    }
}

void get_sum(int cur, int pnode) {
    for (int i = 0; i < graph[cur].size(); ++i) {
        if (graph[cur][i].x == pnode) continue;
        int next = graph[cur][i].x;
        int cost = graph[cur][i].y;
        ll csum = sum[cur];
        csum -= cost * cnt[next];
        csum += (N - cnt[next]) * cost;
        sum[next] = csum;
        get_sum(next, cur);
    }
    mn = min(mn, sum[cur]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (1) {
        cin >> N;
        if (N == 0) break;

        graph.clear();
        graph.resize(N);
        cnt.clear();
        sum.clear();
        cnt = sum = vector<ll>(N);
        mn = 1e18;
        for (int i = 0; i < N - 1; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            graph[a].push_back({b, c});
            graph[b].push_back({a, c});
        }

        get_tree(0, 0);
        get_sum(0, 0);

        cout << mn << "\n";
    }

    return 0;
}