[伯俊]#11438 LCA 2
質問する
N(2≦N≦100000)個の頂点からなるツリーが与えられる.ツリーの各頂点は1番からN番まで、ルートは1番です.
2つのノードの2つのM(1≦M≦100000)が与えられた場合、出力された2つのノードの最も近い共通の祖先は何回であるか.
入力
1行目にはノード数Nが与えられ、次の行にはツリーに接続された2つの頂点が与えられる.次の行は最近の共通の祖先のペアを知りたい個数Mを与え、次の行Mは頂点ペアを与える.
しゅつりょく
M行に順次入力される2つの頂点に最も近い共通の祖先を出力します.
入力例1
15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15
サンプル出力1
2
4
2
1
3
1
に答える
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
static ArrayList<Integer>[] graph;
static int N;
static boolean[] visited;
static int[][] parent;
static int[] depth;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
depth = new int[N+1];
parent = new int[N+1][18];
visited = new boolean[N+1];
graph = new ArrayList[N+1];
for(int i=1; i<=N; i++)
graph[i] = new ArrayList<>();
for(int i=0; i<N-1; i++) {
String[] input = br.readLine().split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
graph[a].add(b);
graph[b].add(a);
}
dfs(1, 0);
make_tree();
int M = Integer.parseInt(br.readLine());
for(int i=0; i<M; i++) {
String[] input = br.readLine().split(" ");
int a = Integer.parseInt(input[0]);
int b = Integer.parseInt(input[1]);
if(depth[a]<depth[b]) {
sb.append(lca(b, a)+"\n");
}
else {
sb.append(lca(a, b)+"\n");
}
}
System.out.print(sb);
}
static int lca(int a, int b) {
int diff = depth[a] - depth[b];
for(int i=0; diff>0; i++) {
if((diff|1)==diff) {
a = parent[a][i];
}
diff >>= 1;
}
if(a==b) return a;
for(int i=17; i>=0; i--) {
if(parent[a][i]!=parent[b][i]) {
a = parent[a][i];
b = parent[b][i];
}
}
return parent[a][0];
}
public static void make_tree(){
for(int j=1; j<18; j++){
for(int i=1; i<=N; i++){
parent[i][j] = parent[parent[i][j-1]][j-1];
}
}
}
public static void dfs(int temp, int d){
visited[temp] = true;
depth[temp] = d;
for(int next : graph[temp]){
if(!visited[next]){
parent[next][0] = temp;
dfs(next, d+1);
}
}
}
}
Reference
この問題について([伯俊]#11438 LCA 2), 我々は、より多くの情報をここで見つけました https://velog.io/@pss407/백준11438-LCA-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol