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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.*;
import java.io.*;

//lca
public class Main {
	static int N=(int)(1e5+10);
	static ArrayList<Integer> node[];
	public static void main(String args[]) {
		int n=in.nextInt();
		node=new ArrayList[n+10];
		for(int i=1;i<n;i++) {
			int u=in.nextInt();
			int v=in.nextInt();
			if(node[u]==null) node[u]=new ArrayList<>();
			if(node[v]==null) node[v]=new ArrayList<>();
			node[u].add(v);
			node[v].add(u);
		}
		int q=in.nextInt();
		init(n);
		
		
		while(q-->0) {
			int l=in.nextInt(),r=in.nextInt();
			out.println(lca(l,r));
		}
		
		out.flush();
	}
	static int dep[];
	static int fa[][];
	static void init(int n) {
		dep=new int[n+10];
		fa=new int[n+10][30];
		dfs(1,0);
		
		
	}
	
	static void dfs(int u,int f) {
		fa[u][0]=f;
		dep[u]=dep[f]+1;
		
		for(int k=1;k<=20;k++) {
			fa[u][k]=fa[fa[u][k-1]][k-1];
		}
		
		for(int v:node[u]) {
			if(v==f) continue;
			dfs(v,u);
		}
	}
	
	static int lca(int x,int y) {
		if(x==y) return x;
		if(dep[x]<dep[y]) {
			int tmp=x;
			x=y;
			y=tmp;
		}
		for(int k=20;k>=0;k--) {
			if(dep[fa[x][k]]>=dep[y]) {
				x=fa[x][k];
			}
		}
		if(x==y) return x;
		for(int k=20;k>=0;k--) {
			if(fa[x][k]!=fa[y][k]) {
				x=fa[x][k];
				y=fa[y][k];
			}
		}
		return fa[x][0];
	}
	
	
	
	
	
	
	
	static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	static input in=new input();
	static class input{
		static BufferedReader br;
		static StringTokenizer st;
		input(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			String str="";
			while(st==null||!st.hasMoreElements()) {
				try {
					str=br.readLine();
				}catch(Exception e) {
					e.printStackTrace();
				}
				st=new StringTokenizer(str);
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}