[백준/BOJ] 27730 견우와 직녀 C++ 풀이

[문제 링크]
https://www.acmicpc.net/problem/27730

[설명]
두 개의 트리 T1, T2에 대하여 각각 한 노드를 선택해 연결한 후 T1의 모든 정점과 T2의 모든 정점의 거리의 합을 구하는 문제이다. T1은 n개의 노드, T2는 m개의 노드를 가지고 있다. T1에서 A를 선택 후 다른 정점들로부터 A의 거리를 구하고, T2에서 B를 선택했을 때에 대해서도 마찬가지로 거리를 구한다. 각 거리를 D1, D2라고 한다면 A, B를 연결했을 때의 거리는 (D1 * n + D2 * m + m * n)이 된다. 따라서 D1, D2가 최소가 되도록 A, B를 선택하면 된다.

각각의 노드에 대해서 D를 구하기 위해 먼저 아무 노드에서의 D를 구한다. 이때 그 노드를 루트 노드로 정하고 각각의 서브트리에 대해서 재귀적으로 실행하면 된다. 한 노드에서 이 값은 (자식 노드를 루트로 하는 서브트리의 노드의 개수 * 연결된 가중치 + 그 자식노드의 값)을 더해주며 구한다. 이는 dfs를 통해 구한다. 그리고 이를 구하면 다른 노드들의 D는 (부모 노드의 D + (전체 노드의 개수 - 2 * 그 노드의 서브트리의 노드 개수) * 가중치)가 된다. 이는 bfs를 통해 구한다.

[코드]

#include<iostream>
#include<vector>
#include<queue>
#define ll long long
using namespace std;

struct info {
	int x;
	ll dis;
};

vector<info> graph[2][100001];
int node[2];
ll n[2], res[2][100001], dp[2][100001], cnt[2][100001], ans[2];
bool visited[2][100001];
queue<int> q;

void input(int t) {
	int i, a, b; ll c;
	for (i = 1; i < n[t]; i++) {
		cin >> a >> b >> c;
		graph[t][a].push_back({ b,c });
		graph[t][b].push_back({ a,c });
	}
}

void dfs(int t, int a) {
	visited[t][a] = 1;
	cnt[t][a] = 1;
	for (auto& iter : graph[t][a]) {
		if (visited[t][iter.x]) continue;
		dfs(t, iter.x);
		cnt[t][a] += cnt[t][iter.x];
		dp[t][a] += dp[t][iter.x] + iter.dis * cnt[t][iter.x];
	}
	visited[t][a] = 0;
}

void find_min(int t, int a) {
	q.push(a);
	ans[t] = res[t][a] = dp[t][a];
	node[t] = 1;
	visited[t][a] = 1;
	while (!q.empty()) {
		a = q.front();
		q.pop();
		for (auto& iter : graph[t][a]) {
			if (visited[t][iter.x]) {
				res[t][a] = res[t][iter.x] + iter.dis * (n[t] - 2 * cnt[t][a]);
				if (ans[t] > res[t][a]) {
					ans[t] = res[t][a];
					node[t] = a;
				}
			}
			else q.push(iter.x);
			visited[t][iter.x] = 1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	for (int i = 0; i < 2; i++) {
		cin >> n[i];
		input(i);
		dfs(i, 1);
		find_min(i, 1);
	}
	cout << node[0] << ' ' << node[1] << '\n' << ans[0] * n[1] + ans[1] * n[0] + n[0] * n[1];
}