인프런 커뮤니티 질문&답변

P11438 문제 교재 코드 그대로 쳤는데 시간초과가 발생하네요 ㅜ

어딜 고쳐야 할까요 ㅠ

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

public class Main {
	static ArrayList<Integer>[] tree;
	static int[] depth;
	static int kmax;
	static int[][] parent;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 노드의 수
		tree = new ArrayList[N + 1];
		for(int i = 1; i <= N; i++) {
			tree[i] = new ArrayList<Integer>();
		}
		StringTokenizer st;
		// 1. 인접리스트에 그래프 데이터 저장하기
		for(int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			tree[s].add(e);
			tree[e].add(s);
		}
		depth = new int[N+1];
		visited = new boolean[N + 1];
		int temp = 1;
		kmax = 0;
		while (temp <= N) {  // 최대 가능 depth 구하기
			temp <<= 1;
			kmax++;
		}
		parent = new int[kmax + 1][N + 1];
		// 2. depth와 바로 윗 부모 bfs로 구하기
		bfs(1);
		// 3. 2^k 부모 구하기
		for(int k = 1; k <= kmax; k++) {
			for(int n = 1; n <= N; n++) {
				parent[k][n] = parent[k - 1][parent[k - 1][n]];
			}
		}
		int M = Integer.parseInt(br.readLine());
		// 4. 질의 수행하기
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int LCA = excuteLCA(a, b);
			System.out.println(LCA);
		}
	}
	static int excuteLCA(int a, int b) {
		// 더 깊은 depth가 뒤에 오도록 변경
		if (depth[a] > depth[b]) {
			int temp = a;
			a = b;
			b = temp;
		}
		for(int k = kmax; k >= 0; k--) {  // 높이 빠르게 맞추기
			if(Math.pow(2, k) <= depth[b] - depth[a]) {
				if(depth[a] <= depth[parent[k][b]]) {
					b = parent[k][b];
				}
			}
		}
		for(int k = kmax; k >=0; k--) {  // 조상 빠르게 찾기
			// 최대 위로 올라가서 같은 부모를 가리키면 k를 1씩 감소하며 다른 지점을 찾음
			if(parent[k][a] != parent[k][b]) {
				a = parent[k][a];
				b = parent[k][b];
			}
		}
		// 여기 온 것은 k = 0일때 고려
		// case 1. k=0, 둘이 같은 노드를 가리킴 -> 그곳이 최소 공통 조상
		// case 2. k=0, 둘이 다른 노드를 가리킴 -> 바로 위에가 최초 공통 조상 -> 2^0 위에 보기
		int LCA = a;
		if(a != b) {
			LCA = parent[0][LCA];
		}
		return LCA;
	}
	// bfs 구현
	private static void bfs(int node) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(node);
		visited[node] = true;
		int level = 1;
		int now_size = 1;
		int count = 0;
		while(!queue.isEmpty()) {
			int now_node = queue.poll();
			for(int next : tree[now_node]) {
				if(!visited[next]) {
					visited[next] = true;
					queue.add(next);
					parent[0][next] = now_node;  // 부모 노드 저장하기
					depth[next] = level;  // 노드 depth 저장하기
				}
			}
			count++;
			// 자식 노드 모두 검사했는지 확인
			if(count == now_size) {
				count = 0;
				now_size = queue.size();
				level++;
			}
		}
	}
}