经典LCA操作。。
贴AC代码
import java.lang.reflect.Array;
import java.util.*;
public class POJ1330 {
// 并查集部分
static int[] p;
static int find(int u){
if(p[u]!=u){
p[u] = find(p[u]);
}
return p[u];
}
static class Edge{
int to;
int next;
}
// 链式前向星
static int[] head;
static Edge[] edges; static boolean[] vist;
// 所求LCA的两点
static int qfrom;
static int qto;
// 找根
static boolean[] isroot; static boolean LCA(int u){
// 在以自己为根的子树中计算LCA
// 如果没找到就回溯到父节点，再向下去兄弟子树计算
// 先建立以自己为代表的并查集
p[u]=u;
vist[u]=true; for(int k=head[u];k>=0;k=edges[k].next){
int to = edges[k].to;
if(!vist[to]) {
// 计算子树
// 如果在某棵子树计算过程中算出结果，就返回true
if(LCA(to))
return true;
// 子树计算完，把子树的并查集代表节点设为当前节点
p[to] = u;
}
}
// 所有子树计算完毕，还没发现结果
// 试试用当前节点计算结果
if(u == qfrom){
if(vist[qto]){
System.out.println(find(qto));
return true;
}
}else if(u==qto){
if(vist[qfrom]){
System.out.println(find(qfrom));
return true;
}
} // 还是没算出结果，向上回溯，准备去兄弟子树计算
return false;
} public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
while (n-- > 0){
int m = sc.nextInt();
p = new int[m+1];
head = new int[m+1];
Arrays.fill(head,-1);
edges = new Edge[m];
vist = new boolean[m+1];
isroot = new boolean[m+1];
Arrays.fill(isroot,true);
// 链式前向星构有向图
for(int i=0;i<m-1;i++){
int from = sc.nextInt();
int to = sc.nextInt();
Edge edge = new Edge();
edge.to=to;
edge.next=head[from];
edges[i]=edge;
head[from]=i;
// 有父节点的不是根
isroot[to]=false;
}
qfrom = sc.nextInt();
qto = sc.nextInt();
// 找根
int root=0;
for(int i=1;i<isroot.length;i++){
if(isroot[i]) {
root = i;
break;
}
}
// 计算LCA
LCA(root);
}
}
}