[백준/BOJ] 백준 20188번 : 등산 마니아

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

20188번: 등산 마니아

각 간선이 길에 몇 번 포함되는지 개수를 구하는 방법으로 문제를 해결했다. 부모 노드와 자식 노드를 연결하는 간선은 두 정점을 모두 부모 노드 위쪽(부모 노드 포함)에서 고르는 경우를 제외하고 모두 사용되므로 전체에서 두 점을 구하는 경우((n * (n-1))/2) - 부모노드 위쪽에서 두 점을 구하는 경우(((n - sub_tree_size[there]) * (n - sub_tree_size[there] - 1)) / 2)를 계산하여 문제를 해결했다.

 

코드

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

int n;
vector<int> adj[300001];
vector<int> maked(300001, 0);
vector<int> children[300001];
vector<int> sub_tree_size(300001, 0);
long long result = 0;

//here가 루트인 서브트리를 만든다
//서브트리의 크기 반환
int MakeTree(int here)
{
	maked[here] = 1;
	sub_tree_size[here] += 1;

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

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

		sub_tree_size[here] += MakeTree(there);
		children[here].push_back(there);
	}

	return sub_tree_size[here];
}

//각 간선이 몇번 쓰이는 지에 대한 방법으로 문제를 해결
void Solve(int here)
{
	for (int i = 0; i < children[here].size(); i++)
	{
		int there = children[here][i];

		//here과 there을 연결하는 간선은 두 정점을 here 위쪽에서 사용하는 경우를 제외하고 모두 사용된다
		//전체에서 두 점을 구하는 경우((n * (n-1))/2) - here 위쪽에서 두 점을 구하는 경우(((n - sub_tree_size[there]) * (n - sub_tree_size[there] - 1)) / 2)
		result += ((((long long)n * (long long)(n - 1)) / 2) - (((long long)(n - sub_tree_size[there]) * (long long)(n - sub_tree_size[there] - 1)) / 2));

		Solve(there);
	}
}

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

	cin >> n;

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

		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	MakeTree(1);
	Solve(1);

	cout << result;

	return 0;
}