解：这里的树是有根树，首先由输入创建树存储结构，再对于给定的x和y结点，求LCA的过程如下：（1）求出x结点的层次1x，y结点的层次ly。（2）若1x≠1y，将较高层次的结点上移直到它们处于相同层次。（3）若x≠y，再将它们同步上移直到x=y。这样的x或者y结点就是LCA。从上述过程看出，主要涉及结点上移操作，为此树采用双亲存储结构较合适。由于结点是通过编号唯一标识的，并且N个结点的编号是1～N，所以直接采用int类型的parent数组作为双亲存储结构，parent[表示结点i的双亲结点编号。那么如何确定根结点呢？任何一个结点i有双亲，则parent[]一定是1～N的整数，为此将parent数组所有元素初始化为-1，如果一个结点的双亲father[为-1，则结点i就是根结点
解：这里的树是有根树，首先由输入创建树存储结构，再对于给定的x和 y结点，求LCA的过程如下： （1）求出x结点的层次lx，y结点的层次ly。 （2）若lx≠ly，将较高层次的结点上移直到它们处于相同层次。 （3）若x≠y，再将它们同步上移直到x=y。这样的x或者y结点就是LCA。 从上述过程看出，主要涉及结点上移操作，为此树采用双亲存储结构较 合适。由于结点是通过编号唯一标识的，并且N个结点的编号是1～N，所以 直接采用int类型的parent数组作为双亲存储结构，parent[i]表示结点i 的双亲结点编号。 那么如何确定根结点呢？任何一个结点i有双亲，则parent[i]一定是 1～N的整数，为此将parent数组所有元素初始化为-1，如果一个结点i的双 亲father[i]为-1，则结点i就是根结点
101016111611结点16和7的LCA是结点4！
8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13 8 5 9 6 4 7 10 1 15 11 16 2 3 12 14 13 -1 结点16和7的LCA是结点4！
import java.util.*;import java.util.Scanner;public class Main{ final static int MAxN=10005;1/树的双亲存储结构static int [] parent=new intMAxN];1/求x结点的层次public static int Level(int x) int cnt=o;1/找到根为止while(x!=-1)1/结点x上移{ x=parent[x];1/累计上移的次数就是原×结点的层次cnt++;return cnt;
import java.util.*; import java.util.Scanner; public class Main { final static int MAXN=10005; static int [] parent=new int[MAXN]; //树的双亲存储结构 public static int Level(int x) //求x结点的层次 { int cnt=0; while(x!=-1) //找到根为止 { x=parent[x]; //结点x上移 cnt++; //累计上移的次数就是原x结点的层次 } return cnt; }
public staticintsolve（intx,inty）//求x和y结点的最近公共祖先结点{ int lx=Level(x);//求x结点的层次1xint ly=Level(y);/求y结点的层次1ywhile (lx>ly)//将较高层次的x结点上移{ x=parent[x];1x--;7while (ly>lx)//将较高层次的y结点上移{ y=parent[y];ly--;while (x!=y)//当x和y移到相同层次，再找LCAx=parent[x];y=parent[y];+return x;
public static int solve(int x,int y) //求x和y结点的最近公共祖先结点 { int lx=Level(x); //求x结点的层次lx int ly=Level(y); //求y结点的层次ly while (lx>ly) //将较高层次的x结点上移 { x=parent[x]; lx-; } while (ly>lx) //将较高层次的y结点上移 { y=parent[y]; ly-; } while (x!=y) //当x和y移到相同层次，再找LCA { x=parent[x]; y=parent[y]; } return x; }
public static void main(string[] args)( Scanner fin = new Scanner(System.in);int T,N,a,b,x,y;T=fin.nextInt();while (T-->0){ N=fin.nextInt();1/初始化N个结点的双亲为-1for(int i=o;i<=N;i++)parent[i]=-1;1/输入N-1条边，创建双亲存储结构for (int i=l;i<N;i++)1/输入一条边a=fin.nextInt();b=fin.nextInt();parent[b]=a;1/输入查询x=fin.nextInt();心花怒放y=fin.nextInt();//求LCAint ans=solve(x,y);&31/输出结果System.out.println(ans):
public static void main(String[] args) { Scanner fin = new Scanner(System.in); int T,N,a,b,x,y; T=fin.nextInt(); while (T->0) { N=fin.nextInt(); for (int i=0;i<=N;i++) //初始化N个结点的双亲为-1 parent[i]=-1; for (int i=1;i<N;i++) //输入N-1条边,创建双亲存储结构 { a=fin.nextInt(); //输入一条边 b=fin.nextInt(); parent[b]=a; } x=fin.nextInt(); //输入查询 y=fin.nextInt(); int ans=solve(x,y); //求LCA System.out.println(ans); //输出结果 } } }