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

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

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

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

코드

#include #include #include using namespace std; int n; vector adj[300001]; vector maked(300001, 0); vector children[300001]; vector 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; }

from http://geniusjo-story.tistory.com/530 by ccl(A) rewrite - 2021-09-04 12:26:50