[백준/BOJ] 백준 7812번 : 중앙 트리

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

7812번: 중앙 트리

0번 정점이 루트인 트리를 만들고 트리를 만들면서 sub_tree_node[here]에 here가 루트인 서브 트리의 노드의 개수를 저장하고, result에는 0번 정점에서부터 각 정점으로 가는 비용을 저장한다. 그리고 루트에서 연결된 정점들 부터 Solve(int before, int here, int before_here_cost) (before : 부모 노드(이전 노드), here : 현재 노드, before_here_cost : 부모노드와 현재 노드 사이 간선의 비용)을 이용해여 here가 기준일 때 각 정점으로 가는 비용을 구하는데, 방법은 이전 결과값에서 (before_here_cost * sub_tree_node[here])값이 감소하고 (before_here_cost * (sub_tree_node[root] - sub_tree_node[here]))값이 증가한다는 것을 이용하여 문제를 해결했다.

 

참고 그림

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
long long cache[10000];
vector<pair<int, int>> adj[10000];
vector<pair<int, int>> tree[10000];
int maked[10000];
int sub_tree_node[10000];
long long result;
vector<long long> output;
int root = 0;

void Pre()
{
	for (int i = 0; i < 10000; i++)
	{
		cache[i] = -1;
		adj[i].clear();
		tree[i].clear();
		maked[i] = 0;
		sub_tree_node[i] = 0;
		result = 0;
	}
}

//here가 루트인 트리 만들기
//here가 루트인 서브트리의 노드 개수 반환
int Make_tree(int here, long long sum)
{
	maked[here] = 1; //트리로 만들어진 노드 표시
	sub_tree_node[here] = 1; //자기 자신

	for (int i = 0; i < adj[here].size(); i++)
	{
		int cost = adj[here][i].first;
		int there = adj[here][i].second;

		if (maked[there] == 0)
		{
			result += (sum + (long long)cost); //이렇게 하면, 다 계산하고 나면 result에는 진짜 트리의 루트(0번 정점)에서 각 정점으로 가는 비용이 저장된다

			tree[here].push_back(make_pair(cost, there));
			sub_tree_node[here] += Make_tree(there, (sum + (long long)cost));
		}
	}

	return sub_tree_node[here];
}

void Solve(int before, int here, int before_here_cost)
{
	//이전 결과값에서 (before_here_cost * sub_tree_node[here])값이 감소하고 (before_here_cost * (sub_tree_node[root] - sub_tree_node[here]))값이 증가한다
	cache[here] = cache[before] - ((long long)before_here_cost * (long long)sub_tree_node[here]) + ((long long)before_here_cost * (long long)(sub_tree_node[root] - sub_tree_node[here]));

	result = min(result, cache[here]);

	//here에서 연결된 정점을 기준으로 값을 구한다
	for (int i = 0; i < tree[here].size(); i++)
	{
		int there = tree[here][i].second;
		int cost = tree[here][i].first;

		Solve(here, there, cost);
	}
}


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

	while (1)
	{
		Pre();

		cin >> n;

		if (n == 0)
			break;

		for (int i = 0; i < n - 1; i++)
		{
			int a, b, w;

			cin >> a >> b >> w;

			adj[a].push_back(make_pair(w, b));
			adj[b].push_back(make_pair(w, a));
		}

		Make_tree(root, 0); //root(0번) 정점이 루트인 트리 만들기
		cache[root] = result; //root(0번) 정점이 루트인 트리를 만들면 result에는 루트(0번 정점)에서 각 정점으로 가는 비용이 저장된다

		//루트에서 연결된 정점을 기준으로 값을 구한다
		for (int i = 0; i < tree[root].size(); i++)
		{
			int there = tree[root][i].second;
			int cost = tree[root][i].first;
			Solve(root, there, cost);
		}

		output.push_back(result);
	}

	for (int i = 0; i < output.size(); i++)
		cout << output[i] << "\n";

	return 0;
}