Description
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor
of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node
x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common
ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest
common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers
whose nearest common ancestor is to be computed.
Output
Sample Input
2 16 1 14 8 5 10 16 5 9 4 6 8 4 4 10 1 13 6 15 10 11 6 7 10 2 16 3 8 1 16 12 16 7 5 2 3 3 4 3 1 1 5 3 5
Sample Output
4 3
#include<cstdio> #include<iostream> #include<cstring> #define N 10010 using namespace std; int fa[N]; int h[N]; int f[N][20]; int n,root,ax,ay; inline void dfs(int x) { if (h[x])return; dfs(fa[x]); h[x]=h[fa[x]]+1; } inline int jump() { if (ax==ay) return ax; for (int i=0;i<=15;i++) if (f[ax][i]==f[ay][i]) { if(i==0)return f[ax][i]; ax=f[ax][i-1];ay=f[ay][i-1]; return jump(); } } int main() { int T;scanf("%d",&T); while (T--) { memset(f,0,sizeof(f)); memset(h,0,sizeof(h)); memset(fa,0,sizeof(fa)); scanf("%d",&n); for (int i=1;i<n;i++) { int x,y;scanf("%d%d",&x,&y); fa[y]=x; } scanf("%d%d",&ax,&ay); for (int i=1;i<=n;i++)if(!fa[i])root=i; h[root]=1; for (int i=1;i<=n;i++)if (!h[i])dfs(i); for (int i=1;i<=n;i++)f[i][0]=fa[i]; f[root][0]=root; for (int i=1;i<=15;i++) for (int j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1]; if (h[ax]<h[ay])swap(ax,ay); int c=h[ax]-h[ay]; for(int i=20;i>=0;i--)if (c&(1<<i))ax=f[ax][i]; printf("%d\n",jump()); } }