[백준]LCA와 쿼리(15480)

문제 링크 : [백준]LCA와 쿼리(15480)

15480번: LCA와 쿼리

문제 설명

N개의 노드로 이루어진 트리가 주어집니다.

M개의 쿼리가 주어지는데, 루트 정보와 두 노드가 주어지면, 주어진 루트를 기준으로 두 노드의 LCA를 출력합니다.

입력

N(노드 갯수, 1 <= N <= 100,000)

A_i B_i(간선 정보

M(쿼리의 갯수, 1 <= M <= 100,000)

R_i U_i V_i(쿼리 정보) 

7
1 2
2 3
2 4
1 5
5 6
4 7
5
1 2 7
3 1 5
2 1 7
5 6 2
6 2 3

 

출력

2
1
2
5
2

 

카테고리

#LCA

 

시간 복잡도 상한

O(MlogN)

 

해결 방법

1. 일단 LCA정보는 필요 할 것 같으니까 만들어둡니다.
2. 처음에는 루트가 두 노드의 경로에 있는 경우, 두 노드가 일직선에 있고, 루트가 그 밑에 있는 경우 등등 해서 만들어 보았으나, 쪼끔 맞고 틀립니다.
3. 좀 더 공통적인 규칙을 찾아서 만들어 보도록 합니다.
4. 주어진 노드가 세개이고, 각각의 LCA를 만드는 경우도 세가지가 있습니다.
   1. X : 루트와 A노드의 LCA
   2. Y : 루트와 B노드의 LCA
   3. Z : A, B 노드의 LCA
5. 세 노드간의 관계는 또 세가지가 있습니다.
   1. A, B 모두 루트의 자식인 경우, Z가 답이 됩니다.
      1. Z는 깊이가 낮아도 루트의 깊이보다 낮지 않습니다.
      2. X, Y는 루트 노드가 됩니다.
   2. A, B 중 하나만 자식인 경우, 루트가 답이 됩니다.
      1. A, B 노드 중 루트의 자식의 LCA는 루트 노드가 되며, 그렇지 않은 노드는 루트보다 부모 노드가 됩니다.
      2. Z는 1에서 루트의 자식이 아닌 노드와의 LCA 노드가 됩니다.
   3. A, B 둘 다 루트의 자식이 아닌 경우, 루트와 두 노드의 LCA 중 루트에 가까운 노드가 답이 됩니다.(깊이가 깊은 노드)
      1. Z는 적어도 X, Y 중 깊이가 깊은 노드보다 깊이가 깊지 않습니다.
6. 위 경우들을 종합해 볼 때, X, Y, Z 중 깊이가 가장 깊은 노드를 구하면 됩니다.

시간복잡도

O(MlogN)

코드

#include<iostream>
#include<vector>
#define N 100001
using namespace std;
int n,m,a,b,c,d[N],L[N][18],i,x,y,z;
vector<int>v[N];
void r(int p,int f){
    d[p]=d[f]+1;
    L[p][0]=f;
    for(int i=1;i<18;i++)L[p][i]=L[L[p][i-1]][i-1];
    for(int x:v[p])if(x!=f)r(x,p);
}
int l(int a,int b){
    if(d[a]>d[b])swap(a,b);
    for(i=17;i>=0;i--)if(d[b]-d[a]>=(1<<i))b=L[b][i];
    if(a==b)return a;
    for(i=17;i>=0;i--)if(L[b][i]!=L[a][i])a=L[a][i],b=L[b][i];
    return L[a][0];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<n;i++)cin>>a>>b,v[a].push_back(b),v[b].push_back(a);
    r(1,0);
    cin>>m;
    while(m--){
        cin>>a>>b>>c;
        x=l(a,b);y=l(b,c);z=l(a,c);
        a=d[x]>d[y]?x:y;
        a=d[a]>d[z]?a:z;
        cout<<a<<"\n";
    }
}