백준1761 정점들의 거리

작성일 | In

문제 링크

  • http://icpc.me/1761

사용 알고리즘

  • LCA

시간복잡도

  • 전처리 O(NlogN)
  • 쿼리 O(logN)

풀이

트리에서 루트부터 어떤 정점 x까지의 거리를 dist[x]라고 합시다.
그러면 정점 u부터 v까지 경로의 길이는 dist[u] + dist[v] - 2dist[lca(u, v)] 입니다.
lca를 잘 구현해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

int dep[40404];
int chk[40404];
int dist[40404];
int dp[40404][20];
vector<p> g[40404];
int n;

void dfs(int now, int d, int c){
	chk[now] = 1;
	dep[now] = d;
	dist[now] = c;
	for(auto i : g[now]){
		int nxt = i.x;
		int cst = i.y;
		if(chk[nxt]) continue;
		dp[nxt][0] = now;
		dfs(nxt, d+1, c+cst);
	}
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	int diff = dep[v] - dep[u];
	for(int i=0; diff; i++){
		if(diff & 1) v = dp[v][i];
		diff >>= 1;
	}
	if(u == v) return u;
	for(int i=19; i>=0; i--){
		if(dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
	}
	return dp[u][0];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	dep[1] = 1, dp[1][0] = 0; chk[1] = 1; dist[1] = 0;
	for(int i=0; i<n-1; i++){
		int a, b, c; cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	dfs(1, 0, 0);
	for(int j=1; j<20; j++){
		for(int i=1; i<=n; i++){
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}

	int m; cin >> m;
	while(m--){
		int a, b; cin >> a >> b;
		int aa = dist[a], bb = dist[b];
		int c = lca(a, b);
		//cout << c << " ";
		int cc = dist[c];
		int res = aa + bb - 2*cc;
		//cout << aa << " " << bb << " " << cc << " ";
		cout << res << "\n";
	}
}