LCA
백준 3176번 도로 네트워크 문제풀이
[3176 도로 네트워크] https://www.acmicpc.net/problem/3176 .
LCA를 구하고 그 때 Sparse table을 이용해보자!
구간 최대, 최소를 구할 때 놀랍게도 전처리를 해두면 O(1)에 구할 수 있는 방법이 있다.
그것이 바로 sparse table이고 최대, 최소는 겹치는 구간이 있어도 상관없기 때문에 겹치는 구간 2개를 이용하는 것이다.
문제상황 파악하기.
도시와 도로가 트리형태로 주어져있고 한 도시에서 다른 도시로 가는 쿼리가 주어지면 경로 상의 가장 짧은 도로와 가장 긴 도로를 출력하면 된다.
K가 최대 10만이므로 최대 O(N(logN)^2))정도에 해결할 수 있다.
한 도시에서 다른 도시로 간다고 하면 둘의 최소 공통 조상을 무조건 지나기 때문에 LCA를 이용할 수 있다.
LCA가 뭐길래
lowest common ancester(최소 공통 조상)이다.
제일 가까운 부모라는 것이다.
구하는 방법은 간단하다. 만날 때까지 위로 올리면 된다.
- u, v의 깊이가 다르면 깊은 것을 올린다.
- 깊이가 같아지면 u==v가 될때까지 동시에 올린다.
위 논리를 이용한 것이 아래 코드이다.
1
2
3
4
5
6
7
8
9
10
11
int LCA(int u, int v){
if(depth[u]<depth[v]) swap(u, v); //u가 더 깊은거라고 하자
int diff = depth[u]-depth[v];
for(int i=0;i<20;i++) if(diff&(1<<i)) u = P[i][u]; //차이 만큼 올라간다.(1번 과정)
if(u==v) return u;
for(int i=19;i>=0;i--) if(P[i][u]!=P[i][v]){ //같아질 떄까지 u, v를 동시에 옮긴다.
u = P[i][u];
v = P[i][v];
}
return P[0][u]; //같아진것을 리턴한다.
}
아이디어 얻기.
일단 두 정점사이 길이 하나밖에 없고 LCA는 무조건 지난다.
따라서 sparse table로 최대 최소를 미리 전처리 해두면 LCA를 구하는 과정에서 최대 최소를 구할 수 있을 것이다.
sparse table은 3개를 만들것이고 다음과 같이 정의한다.
- P[j][i] : i번 정점에서 2^j 위의 조상
- N[j][i] : i번 정점에서 2^j 위의 조상까지 갈 동안 최솟값
- X[j][i] : i번 정점에서 2^j 위의 조상까지 갈 동안 최댓값
주의할 점
위의 코드로 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 987654321;
const int MAX = 100001;
int n, k;
int P[20][MAX], N[20][MAX], X[20][MAX], depth[MAX];
vector<pii> adj[MAX];
void dfs(int here, int parent, int d){
depth[here] = d;
P[0][here] = parent;
for(pii next : adj[here]){
if(next.first==parent) continue;
N[0][next.first] = next.second;
X[0][next.first] = next.second;
dfs(next.first, here, d+1);
}
}
pii LCA(int u, int v){
pii ret;
ret.first = INF;
ret.second = 0;
if(depth[u]<depth[v]) swap(u, v);
int diff = depth[u]-depth[v];
for(int i=0;i<20;i++) if(diff&(1<<i)){ // 깊이를 맞추는 과정
ret.first = min(ret.first, N[i][u]);
ret.second = max(ret.second, X[i][u]);
u = P[i][u];
}
if(u==v){
return ret;
}
for(int i=19;i>=0;i--) if(P[i][u]!=P[i][v]){ // 거슬러 올라가는 과정
ret.first = min(ret.first, N[i][u]);
ret.second = max(ret.second, X[i][u]);
u = P[i][u];
ret.first = min(ret.first, N[i][v]);
ret.second = max(ret.second, X[i][v]);
v = P[i][v];
}
//마지막에 갱신을 하고 리턴해야함
ret.first = min(ret.first, N[0][u]);
ret.second = max(ret.second, X[0][u]);
ret.first = min(ret.first, N[0][v]);
ret.second = max(ret.second, X[0][v]);
return ret;
}
int main(){
fast_io
cin >> n;
for(int i=1;i<n;i++){
int u, v, c;
cin >> u >> v >> c;
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
dfs(1, 1, 1);
N[0][1] = INF;
for(int j=1;j<20;j++){ //전처리 과정 O(NlogN)
for(int i=1;i<=n;i++){
P[j][i] = P[j-1][P[j-1][i]];
N[j][i] = min(N[j-1][i], N[j-1][P[j-1][i]]);
X[j][i] = max(X[j-1][i], X[j-1][P[j-1][i]]);
}
}
cin >> k;
for(int i=0;i<k;i++){ //O(KlogN)
int u, v; cin >> u >> v;
pii res = LCA(u, v);
cout << res.first << ' ' << res.second << '\n';
}
}