BOJ 1761 정점들의 거리

1761.cpp

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

class Node
{
public:
	int child, dist;
	Node() {}
	Node(int c, int d) : child(c), dist(d) {}
};
const int MAX_N = 1000001;
int n, locInTrip[MAX_N], depth[MAX_N], n2s[MAX_N], s2n[MAX_N], ns;
bool visited[MAX_N];
int tree[222222];
vector<vector<Node> >v;
vector<int> tr;
void traverse(int here, int len)
{
	visited[here] = true;
	n2s[here] = ns;
	s2n[ns++] = here;
	
	depth[here] = len;
	locInTrip[here] = tr.size();
	tr.push_back(n2s[here]);

	for (auto there : v[here])
	{
		if (!visited[there.child])
		{
			traverse(there.child, len + there.dist);
			tr.push_back(n2s[here]);
		}
	}
}
int init(int l, int r, int node)
{
	if (l == r) return tree[node] = tr[l];
	return tree[node] = min(init(l, (l + r) / 2, node * 2), init((l + r) / 2 + 1, r, node * 2 + 1));
}
int get(int l, int r, int node, int s, int e)
{
	if (r < s || e < l) return 2e9;
	if (l <= s && e <= r) return tree[node];
	return min(get(l, r, node * 2, s, (s + e) / 2), get(l, r, node * 2 + 1, (s + e) / 2 + 1, e));
}
int LCA(int u, int v)
{
	int lu = locInTrip[u], lv = locInTrip[v];
	if (lu > lv) swap(lu, lv);

	int ans = s2n[get(lu, lv, 1, 0, 2 * n - 2)];
	return depth[u] + depth[v] - 2 * depth[ans];
}
int main()
{
	ios::sync_with_stdio(false);
	int m;
	cin >> n;
	v.resize(1<<((int)ceil(log2(n) + 1)));
	for (int i = 0; i < n-1; i++)
	{
		int x, y, z;

		cin >> x >> y >> z;
		v[x-1].push_back({ y-1,z });
		v[y-1].push_back({ x-1,z });
	}

	traverse(0, 0);
	init(0, 2*n - 2, 1);

	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;

		cin >> a >> b;
		cout << LCA(a-1, b-1) << "\n";
	}
}