문제 URL : https://www.acmicpc.net/problem/15480
15480번: LCA와 쿼리
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(
www.acmicpc.net
문제 접근법 :
루트가 매번바뀌는 문제입니다.
sparse table을 만든후
해당트리의 루트가 r일때 u,v의 lca를 구하는문제인데
lca(r,u) , lca(r,v), lca(u,v)를 구해서
3가지의 lca의 중 가장 depth가 큰노드의 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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define TH 20
vector<int> v[100001],depth;
vector<tuple<int,int,int>> iv;
int n, m;
int parent[TH+1][100001];
void input(){
cin>>n;
int a,b,c;
for(int i=0;i<n-1;i++){
cin>>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
cin>>m;
for(int i=0;i<m;i++){
cin>>a>>b>>c;
iv.push_back({a,b,c});
}
}
void dfs(int cur=1,int p=0,int h=0){
parent[0][cur]=p;
depth[cur]=h;
for(int next:v[cur]){
if(depth[next]==-1)dfs(next,cur,h+1);
}
}
void sparseTable(){
for(int i=1;i<=TH;i++){
for(int j=1;j<=n;j++){
parent[i][j]=parent[i-1][parent[i-1][j]];
}
}
}
int lca(int x,int y){
if(depth[x]>depth[y])swap(x,y);
for(int i=TH;i>=0;i--){
if(depth[y]-depth[x]>=(1<<i)){
y=parent[i][y];
}
}
if(x==y)return x;
for(int i=TH;i>=0;i--){
if(parent[i][x]!=parent[i][y]){
x=parent[i][x];
y=parent[i][y];
}
}
return parent[0][x];
}
void solve(){
depth=vector<int>(n+1,-1);
dfs();
sparseTable();
for(auto[a,b,c]:iv){
vector<pair<int,int>> res;
int ab = lca(a,b);
int ac = lca(a,c);
int bc = lca(b,c);
res.push_back({depth[ab],ab});
res.push_back({depth[ac],ac});
res.push_back({depth[bc],bc});
sort(res.begin(),res.end());
cout<<res.back().second<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 2617 구슬 찾기 (0) | 2023.01.18 |
|---|---|
| 백준 8012 한동이는 영업사원! (0) | 2023.01.18 |
| 백준 14676 영우는 사기꾼? (0) | 2022.11.15 |
| 백준 5525 IOIOI (0) | 2022.11.01 |
| 백준 1007 벡터 매칭 (1) | 2022.11.01 |
