[백준 7812] 중앙 트리

문제

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

7812번: 중앙 트리

 

풀이

1. 0번부터 n - 1번까지 중앙 정점을 옮겨가며 매번 거리를 계산하는게 아니라 0번 정점과 그 외 정점사이의 거리를 구한 후, 중앙 정점을 옮길 때마다 추가/감소되는 비용만 구하면 최소거리인 중앙정점을 구할 수 있습니다.

 

2. 정점을 옮길 때마다 추가/감소되는 비용은 정점과 연결된 간선들의 개수와 관련이 있고, 이는 dfs를 돌려 연결된 간선개수를 찾을 수 있습니다.

 

3.  (u, v)가 cost = c 로 연결되어있고, 중앙 정점을 u번 -> v번 정점으로 옮길 때 드는 비용은 아래와 같습니다.

  (추가되는 비용) = (모든 간선의 개수 - (v에 연결된 간선들의 개수 - 1)) * c = (n - 1 - (sz[v] - 1)) * c

  (감소되는 비용) = (v에 연결된 간선들의 개수) * c  = (-sz[v]) * c

  ∴ (추가되는 비용 + 감소되는 비용) = (n - 2 * sz[v]) * c

 

코드

#include <bits/stdc++.h>
using namespace std;

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

int n, a, b, w, sz[10001];
ll mn, sum;
vector<pii> adj[10001];

void dfs(int u, int p, int s){
	sz[u]= 1;
	for (auto [v,c] : adj[u]){
		if (v == p) continue;
		dfs(v, u, s + c);
		sum += s + c;
		sz[u] += sz[v];
	}
}

void solve(int u, int p, ll co){
	mn = min(mn, co);
	for (auto [v,c] : adj[u]){
		if (v == p) continue;
		solve(v, u, co + (n - 2 * sz[v]) * c);
	}
}

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

	while (1){
		cin >> n;
		if (!n) break;

		memset(sz, 0, sizeof(sz));
		for (int i = 0 ; i < n; i++) adj[i].clear();
		mn = 0x3f3f3f3f3f3f3f3f, sum = 0;
		
		for (int i = 0 ; i < n - 1; i++){
			cin >> a >> b >> w;
			adj[a].push_back({b,w});
			adj[b].push_back({a,w});
		}
		
		dfs(0, -1, 0); // 1. find size
		solve(0, -1, sum); // 2. find ans
		cout << mn << "\n";
	}
}