首页 > 代码库 > POJ 1330 裸的LCA

POJ 1330 裸的LCA

2024-07-14 23:21:46   222人阅读

Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17720 Accepted: 9393

Description

A rooted tree is a well-known data structure in computer science and engineering. An example is shown below: 

 
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

The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., 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

Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.

Sample Input

2161 148 510 165 94 68 44 101 136 1510 116 710 216 38 116 1216 752 33 43 11 53 5

Sample Output

43


题目意思：
给出一棵树，然后求最后位置的两个点最近公共祖先。


刚学LCA算法，拿这道题练练手。
本题采用LCA倍增法。
LCA倍增法思想是：若求x,y在树中的最近公共祖先，那么先把x，y置于同一层，然后向上走，当两点走到一起时，此处即为x,y的最近公共祖先。

实现方法：
采用一个数组f[x][i]即为编号为x的结点向上走1<<i步所到的结点的编号，dep[x]为编号为x的结点在树中的深度。

1、dfs遍历整棵树，在遍历过程中由f[x][i]=f[f[x][i-1]][i-1]算出每个结点走1<<i步所到结点编号（该式由来：f[x][i]为编号为x的结点向上走1<<i步所到的结点，那么不就是编号为x的结点向上走两个1<<i-1么）；由dep[x]=dep[f[x][0]]+1算出每个结点在树中的深度。

2、把所求两个结点x,y置于同一层，然后向上从能上的最高层向下走即for(i=20;i>=0;i--)，若在x,y都向上走1<<i步后两点不重合，那么x,y都等于向上走1<<i步处的结点（我表达能力弱= =，大概意思就是从上到下搜索，由于两点重合处的结点不一定是最近公共祖先，所以向下继续走，若走到1<<i处，低于最近公共祖先，那么两点都移到1<<i处，就这样不断往复，最后达到最近公共祖先）。

代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <iostream> 6 using namespace std; 7 #define N 10005 8 #define M 20      //M最大为20就够了  毕竟1<<20已经是很高一棵树了  9 10 vector<int>ve[N];11 int f[N][M];12 int dep[N];13 14 void init(){15     memset(f,0,sizeof(f));16     memset(dep,0,sizeof(dep));17     for(int i=0;i<N;i++) ve[i].clear();18 }19 20 void dfs(int root){      21     int i;22     dep[root]=dep[f[root][0]]+1;          //求深度  23     for(i=1;i<M;i++) f[root][i]=f[f[root][i-1]][i-1]; //求f[x][i] 24     for(i=0;i<ve[root].size();i++) dfs(ve[root][i]);    //遍历儿子 25 }26 27 int LCA(int x,int y){28     int i, j, k;29     if(dep[x]<dep[y]) swap(x,y);  //保证x的深度大于y 30     k=dep[x]-dep[y];31     for(i=0;i<M;i++){32         if(1<<i&k)          //进行完这一步后，x与y一定在同一层，想一想为什么 33         x=f[x][i];34     }35     if(x==y) return x;36     for(i=M-1;i>=0;i--){         //往复搜索最近公共祖先过程 37         if(f[x][i]!=f[y][i]){38             x=f[x][i];39             y=f[y][i];40         }41     }42     return f[x][0];43 }44 main()45 {46     int t;47     int n;48     int i, j, x, y;49     cin>>t;50     while(t--){51         scanf("%d",&n);52         init();53         int MAX=-1;54         for(i=0;i<n-1;i++){55             scanf("%d %d",&x,&y);56             ve[x].push_back(y);57             f[y][0]=x;58             MAX=max(MAX,x);59             MAX=max(MAX,y);60         }61         int root;62         for(i=1;i<=MAX;i++){63             if(!f[i][0]){64                 root=i;      //找到根结点 65                 break;66             }67         }68         scanf("%d %d",&x,&y);69         dfs(root);         //从根结点开始遍历 70         printf("%d\n",LCA(x,y));71     }72 }

 


联系
我们