K번째 조상 (K-th Ancestor)

import sys
from math import log2, ceil
sys.setrecursionlimit(600000)
input = sys.stdin.readline
​
def main():
  n = int(input())
  adj = [[] for _ in range(n)]
  for _ in range(n - 1):
      a, b = map(int, input().split())
      adj[a-1].append(b-1)
      adj[b-1].append(a-1)
​
  LOG = max(1, ceil(log2(n)) + 1)
  up = [[-1] * LOG for _ in range(n)]
  depth = [0] * n
​
  # iterative DFS
  stack = [(0, -1, False)]
  order = []
  while stack:
      u, p, processed = stack.pop()
      if processed:
          continue
      up[u][0] = p
      order.append((u, p))
      for v in adj[u]:
          if v != p:
              depth[v] = depth[u] + 1
              stack.append((v, u, False))
​
  # 층별 up 테이블 (BFS 순서로 안전)
  for i in range(1, LOG):
      for u in range(n):
          mid = up[u][i-1]
          up[u][i] = up[mid][i-1] if mid >= 0 else -1
​
  def kth(u, k):
      for i in range(LOG):
          if k & (1 << i):
              u = up[u][i]
              if u < 0:
                  return -1
      return u
​
  q = int(input())
  out = []
  for _ in range(q):
      u, k = map(int, input().split())
      ans = kth(u-1, k)
      out.append('-1' if ans < 0 else str(ans + 1))
  print('\n'.join(out))
​
main()

import java.util.*;
import java.io.*;
public class Main {
  static int LOG;
  static int[][] up;
  static int[] depth;
  static List<Integer>[] adj;
​
  static void dfs(int root) {
      int n = adj.length;
      int[] parent = new int[n];
      int[] order = new int[n];
      int idx = 0;
      int[] stack = new int[n];
      int top = 0;
      stack[top++] = root;
      parent[root] = -1;
      boolean[] seen = new boolean[n];
      seen[root] = true;
      while (top > 0) {
          int u = stack[--top];
          order[idx++] = u;
          up[u][0] = parent[u];
          for (int v : adj[u]) if (!seen[v]) {
              seen[v] = true;
              parent[v] = u;
              depth[v] = depth[u] + 1;
              stack[top++] = v;
          }
      }
      for (int i = 1; i < LOG; i++) {
          for (int u = 0; u < n; u++) {
              int mid = up[u][i-1];
              up[u][i] = mid < 0 ? -1 : up[mid][i-1];
          }
      }
  }
​
  static int kth(int u, int k) {
      for (int i = 0; i < LOG; i++) {
          if ((k & (1 << i)) != 0) {
              u = up[u][i];
              if (u < 0) return -1;
          }
      }
      return u;
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine().trim());
      adj = new ArrayList[n];
      for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < n - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken()) - 1;
          int b = Integer.parseInt(st.nextToken()) - 1;
          adj[a].add(b); adj[b].add(a);
      }
      LOG = (int) Math.ceil(Math.log(n) / Math.log(2)) + 1;
      up = new int[n][LOG];
      depth = new int[n];
      dfs(0);
      int q = Integer.parseInt(br.readLine().trim());
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken()) - 1;
          int k = Integer.parseInt(st.nextToken());
          int ans = kth(u, k);
          sb.append(ans < 0 ? -1 : ans + 1).append('\n');
      }
      System.out.print(sb);
  }
}