[BOJ 20188] 등산 마니아

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

20188번: 등산 마니아

 

- 문제 요약

 

동네 뒷 산에는 등산로가 있다.

등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다.

한 오솔길은 두 개의 오두막을 양 방향으로 연결한다.

한 오솔길의 길이는 1이다.

어떤 오두막에서도 다른 모든 오두막으로 하나 이상의 오솔길을 따라 이동하는 것이 가능하다.

오두막들은 1번부터 N번까지 번호가 붙어 있으며, 1번 오두막이 산 정상에 있다.

1번 오두막에서 다른 오두막으로 가는 가장 짧은 길을 따라가면서 거치는 모든 오솔길들은 항상 산을 내려가는 방향이다.

철수가 한 오두막에서 다른 오두막으로 갈 때는 항상 산 정상을 거치는 가장 짧은 길을 따라 간다.

이렇게 간 길의 다양성은 길에 포함된 오솔길의 개수로 정의된다.

두 번 이상 지나간 오솔길은 한 번만 센다는 것에 주의하라.

등산로의 구성을 입력으로 받아 모든 가능한 i, j의 쌍에 대해서(1 ≤ i < j ≤ N), 철수가 i번 오두막에서 j번 오두막으로 가는 길의 다양성의 총합을 계산하는 프로그램을 작성하라.

 

 

- 알고리즘 정리

 

i번 오두막에서 j번 오두막으로 가는 길의 수를 계산하려면 아래의 식을 활용하면 됩니다.

(전체 노드에서 2개의 노드를 선택하는 경우의 수) - (서브트리에서 2개의 노드를 선택하는 경우의 수)

노드는 오두막과 같으므로 노드의 개수는 N입니다.

그러면 전체 노드에서 2개의 노드를 선택하는 경우의 수는 n(n-1)/2입니다.

DFS로 탐색을 돌면서 만들어놓은 식으로 값을 구해 더해주면 됩니다.

+) 자료형은 long long을 사용해 주세요! N이 최대 300,000이므로 int 범위를 벗어날 수도 있습니다.

 

 

- 코드 작성

 

// 완성 코드

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

#define MAX 300001
typedef long long ll;
ll n,result,arr[MAX];
vector<int>v[MAX];

ll f(ll x){
	return x*(x-1)/2;
}

ll dfs(int cur){
	arr[cur]=1;
	for(auto i:v[cur]){
		if(!arr[i]){
			arr[cur]+=dfs(i);
		}
	}
	result+=f(n)-f(n-arr[cur]);
	return arr[cur];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);	
	}
	dfs(1);
	cout<<result-f(n);
}

코드 제출 결과