[백준/BOJ] 백준 15647번 : 로스팅하는 엠마도 바리스타입니다

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

15647번: 로스팅하는 엠마도 바리스타입니다

 

해당 문제의 풀이법은 이전에 작성했던 백준 7812번 : 중앙 트리  (https://geniusjo-story.tistory.com/462) 풀이와 비슷합니다.

 

농장을 트리로 표현한 뒤, 트리로 만들 때 'subtree_size[정점] = 해당 정점이 루트인 서브트리의 크기'와 'subtree_cost[정점] = 해당 정점이 루트인 서브트리에서 루트에서 각 정점으로 가는 비용의 합'을 계산했다.

subtree_cost[루트 노드]을 통해 다른 노드에서 루트 노드로 가는 비용의 합을 계산하였고, 이 값을 기반으로 루트 노드부터 자식 노드를 순서대로 내려오며 해당 자식 노드도 다른 노드에서 해당 노드로 가능 비용의 합을 계산하였다.

이때 기준점이 부모노드일 때 계산한 값을 이용해서 기준점이 자식 노드일 때 계산하는 값은 부모노드 일 때 계산한 값에서 부모노드와 자식노드를 연결하는 간선의 사용 횟수만 변한다는 것을 이용했다.

 

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

int n;
vector<pair<long long, int>> adj[300005];

vector<pair<long long, int>> children[300005];
vector<int> subtree_size(300005, 0);
vector<long long> subtree_cost(300005, 0); //해당 정점이 루트인 서브트리에서 루트에서 각 정점으로 가는 비용을 더한 값
vector<int> maked(300005, 0);

vector<long long> result(300005, 0);

//백준 7812번(중앙 트리) 풀이와 비슷

void MakeTree(int here) {

	maked[here] = 1;
	subtree_size[here] = 1;
	subtree_cost[here] = 0;

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

		if (maked[there] == 1) {
			continue;
		}

		MakeTree(there);

		children[here].push_back(make_pair(cost, there));
		subtree_size[here] += subtree_size[there];
		subtree_cost[here] += ((cost * subtree_size[there]) + subtree_cost[there]);
	}
}

void Solve(int here, int parent, long long here_parent_cost) {

	//이전 연산 결과(부모 노드의 연산 결과)에서 가중치의 추가와 감소 연산
	//기준점이 parent일때 결과값에서 here일때 결과 값으로 바뀌면서 here-parent를 연결하는 간선(해당 간선의 비용:here_parent_cost)의 사용 횟수가 변하는것
	result[here] = result[parent] - (here_parent_cost * (subtree_size[here])) + (here_parent_cost * (n - subtree_size[here]));

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

		Solve(there, here, cost);
	}
}

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

	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int u, v;
		long long d;
		cin >> u >> v >> d;

		adj[u].push_back(make_pair(d, v));
		adj[v].push_back(make_pair(d, u));
	}

	//1번 정점이 루트인 트리를 만든다
	MakeTree(1);

	result[1] = subtree_cost[1];
	for (int i = 0; i < children[1].size(); i++) {
		int there = children[1][i].second;
		long long cost = children[1][i].first;
		Solve(there, 1, cost);
	}

	for (int i = 1; i <= n; i++) {
		cout << result[i] << "\n";
	}

	return 0;
}