백준 3584: 가장 가까운 공통 조상

문제

풀이

tree를 만들기 위해서 root를 알아야 한다.
A부모 B자식 순으로 노드 쌍을 주기 때문에 level[b]++을 해주면
level[node]==0인 노드가 루트이다.
트리를 만들어준 후 lca 알고리즘을 통해 공통 조상을 찾아준다.

---

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            n=Integer.parseInt(br.readLine());
            adj=new ArrayList[n+1];
            for(int i=1;i<n+1;i++)adj[i]=new ArrayList<>();
            level=new int[n+1];
            parent=new int[n+1][17];

            for(int i=0;i<n-1;i++){
                st=new StringTokenizer(br.readLine());
                int a=Integer.parseInt(st.nextToken());
                int b=Integer.parseInt(st.nextToken());
                adj[a].add(b);
                level[b]++;
            }

            int root=0;
            for(int i=1;i<n+1;i++){
                if(level[i]==0){
                    root=i;
                    break;
                }
            }

            makeTree(root,0,1);

            st=new StringTokenizer(br.readLine());
            int a=Integer.parseInt(st.nextToken());
            int b=Integer.parseInt(st.nextToken());
            System.out.println(lca(a,b));
        }


    }

    static int[] level;
    static int[][] parent;
    static int n;
    static ArrayList<Integer>[] adj;

    static void makeTree(int node,int pnode,int lv){
        level[node]=lv;
        parent[node][0]=pnode;

        for(int i=1;i<17;i++){
            parent[node][i]=parent[parent[node][i-1]][i-1];
        }
        for(int a:adj[node]){
            if(a==pnode)continue;
            makeTree(a,node,lv+1);
        }

    }

    static int lca(int a,int b){
        if(a==1 || b==1)return 1;
        if(level[a]<level[b]){
            int tmp=a;
            a=b;
            b=tmp;
        }
        int target=a;
        int compare=b;
        if(level[target]!=level[compare]){
            for(int i=16;i>=0;i--){
                if(level[parent[target][i]]>=level[compare])target=parent[target][i];
            }
        }

        int ret=target;
        if(target!=compare){
            for(int i=16;i>=0;i--){
                if(parent[target][i]!=parent[compare][i]){
                    target=parent[target][i];
                    compare=parent[compare][i];
                }
                ret=parent[target][i];
            }
        }
        return ret;
    }

}

#lca