백준 3176번 : 도로 네트워크 (c++)

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

3176번: 도로 네트워크

문제

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.

다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개 줄에는 서로 다른 두 자연수 D와 E가 주어진다. D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구해서 출력하면 된다.

출력
총 K개 줄에 D와 E를 연결하는 경로에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력한다.

예제 입력 1 
5
2 3 100
4 3 200
1 5 150
1 3 50
3
2 4
3 5
1 2
예제 출력 1 
100 200
50 150
50 100

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;

const int MAX = 100002;
int N, M;
vector <pair<int,int>> node[MAX];
int lca[MAX][21][3];
int depth[MAX];

void dfs(int p, int f) {
	for (int  i = 0; i < node[p].size(); i++)
	{
		pair<int, int> c = node[p][i];
		if (c.first == f) continue;
		depth[c.first] = depth[p] + 1;
		lca[c.first][0][0] = p;
		lca[c.first][0][1] = lca[c.first][0][2] = c.second;
		for (int j = 1; j < 21; j++)
		{
			lca[c.first][j][0] = lca[lca[c.first][j-1][0]][j-1][0];
			lca[c.first][j][1] = min(lca[lca[c.first][j - 1][0]][j - 1][1], lca[c.first][j - 1][1]);
			lca[c.first][j][2] = max(lca[lca[c.first][j - 1][0]][j - 1][2], lca[c.first][j - 1][2]);
		}
		dfs(c.first, p);
	}
}

pair<int,int> find(int a, int b) {
	pair<int, int> r;
	r.first = INT_MAX;
	r.second = 0;
	if (depth[a] > depth[b]) {
		swap(a, b);
	}
	for (int i = 20; i >= 0; i--)
	{
		if ((1 << i) <= depth[b] - depth[a]) {
			r.first = min(r.first, lca[b][i][1]);
			r.second= max(r.second, lca[b][i][2]);
			b = lca[b][i][0];
		}
	}
	if (a == b)	return r;
	for (int i = 20; i >= 0; i--)
	{
		if (lca[a][i][0] != lca[b][i][0]) {
			r.first = min(r.first, min(lca[b][i][1], lca[a][i][1]));
			r.second = max(r.second, max(lca[b][i][2], lca[a][i][2]));
			a = lca[a][i][0];
			b = lca[b][i][0];
		}
	}
	r.first = min(r.first, min(lca[b][0][1], lca[a][0][1]));
	r.second = max(r.second, max(lca[b][0][2], lca[a][0][2]));
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 0; i < N-1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		node[a].push_back({ b,c });
		node[b].push_back({ a,c });
	}
	dfs(1, 0);
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		pair <int, int> x = find(a, b);
		cout << x.first << " " << x.second << "\n";
	}
	return 0;
}