Baekjoon #3584

#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> G;
vector<int> isRoot, depth, parent;
int N, root;

void input() {
    cin >> N;
    G = vector<vector<int>>(N + 1);
    isRoot = vector<int>(N + 1, 1);
    depth = vector<int>(N + 1);
    parent = vector<int>(N + 1);
    for(int i = 1; i < N; i++) {
        int par, child; cin >> par >> child;
        G[par].push_back(child);
        G[child].push_back(par);
        isRoot[child] = 0;
    }
    for(int i = 1; i < N; i++) {
        if(isRoot[i] == 1) root = i;
    }
}

void dfs(int cur, int prev, int dep) {
    depth[cur] = dep;
    for(auto &nxt: G[cur]) {
        if(nxt == prev) continue;
        parent[nxt] = cur;
        dfs(nxt, cur, dep + 1);
    }
}

int getLCA(int a, int b) {
    if(depth[a] > depth[b]) swap(a, b);
    while(depth[a] < depth[b]) b = parent[b];
    while(a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while(T--) {
        input();
        dfs(root, -1, 0);
        int u, v; cin >> u >> v;
        cout << getLCA(u, v) << '\n';
    }

    return 0;
}

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

public class Main {
    static int[] parent;
    static Vector<Integer> comm_1, comm_2;
    public static void main(String[] args) {
        FastReader rd = new FastReader();
        
        int T = rd.nextInt();
        while(T --> 0) { // T번 반복합니다.
            int N = rd.nextInt();
            parent = new int[N + 10];

            // comm_1, comm_2는 공통조상을 찾아야 할 수 comm1, comm2의
            // 자신을 포함한 루트까지의 조상 값을 저장하는 벡터입니다.
            comm_1 = new Vector<Integer>();
            comm_2 = new Vector<Integer>();
            
            for(int i = 0;i < N - 1;i++) {
                int A = rd.nextInt(); // parent
                int B = rd.nextInt(); // child
                parent[B] = A;
            }

            int comm1 = rd.nextInt();
            int comm2 = rd.nextInt();
            // 첫 번째 수의 자신포함 모든 조상를 벡터에 넣습니다.
            // parent[i]값이 0이면 루트라는 뜻입니다.
            while(comm1 != 0) {
                comm_1.add(comm1);
                comm1 = parent[comm1];
            }

            // 두 번째 수의 자신포함 모든 조상를 벡터에 넣습니다.
            while(comm2 != 0) {
                comm_2.add(comm2);
                comm2 = parent[comm2];
            }

            // 두 개의 벡터를 하나씩 비교하면서 가장 먼저 겹치는 수가
            // 첫 번째 공통 조상의 index입니다.
            for(int i : comm_1) {
                if(comm_2.indexOf(i) != -1) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}