Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 9213 | Accepted: 4883 |
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
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<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=12000; struct edge { int t; int next; }; int V; int p[maxn]; edge G[maxn]; int l; int fath[maxn];//父节点 int dep[maxn];//深度 void init() { memset(p,-1,sizeof(p)); memset(fath,-1,sizeof(fath)); l=0; } void addedge(int u,int t,int l) { G[l].t=t; G[l].next=p[u]; p[u]=l; fath[t]=u; } void LCA(int u,int deep) { dep[u]=deep; for(int i=p[u];i!=-1;i=G[i].next) { LCA(G[i].t,deep+1); } } int findLCA(int u,int t) { if(dep[u]<dep[t]) swap(u,t); while(dep[u]>dep[t]) { u=fath[u]; } while(u!=t) { u=fath[u];t=fath[t]; } return t; } int main() { int ci;scanf("%d",&ci); while(ci--&&scanf("%d",&V)==1) { init(); for(int i=1;i<V;i++) { int u,t; scanf("%d%d",&u,&t); addedge(u,t,l++); } for(int i=1;i<=V;i++) { if(fath[i]==-1) { LCA(i,1); break; } } int st,ed; scanf("%d%d",&st,&ed); int tmp=findLCA(st,ed); printf("%d\n",tmp); } return 0; }