CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks
scu


 

#include <iostream>
#include 
<stdio.h>
#include 
<memory.h>
using namespace std;

#define max_size 1010
int d[max_size], p[max_size][10];
int head[max_size];
int cnt;

//构造树时用到的机构体,看过一个大牛用的,感觉很好
struct Edge
{
 
int v;
 
int pre;
}eg[max_size];

//建树的函数
void add(int x, int y)
{
 eg[cnt].v 
= y;
 eg[cnt].pre 
= head[x];
 head[x] 
= cnt++;
}

//dfs()初始整颗数,算出d[1-n], p[1-n][j];
void dfs(int k)
{
 
if (head[k] == 0)
 {
  
return ;
 }
 
int m, x, i, j;
 
for (i = head[k]; i != 0; i = eg[i].pre)
 {
  x 
= eg[i].v;
  p[x][
0= k;
  m 
= k;
  d[x] 
= d[k]+1;
  
for (j = 0; p[m][j] != 0; j++)
  {
   p[x][j
+1= p[m][j];  //利用公式 p[x][j] = p[p[x][j-1]][j-1],这里的m就是p[x][j-1];
   m = p[m][j];
  }
  dfs(x);
 }
}


int find_lca(int x, int y)
{
 
int m,  k;
 
if (x == y)return x;
 
if (d[x] < d[y])
 {
  m 
= x;
  x 
= y;
  y 
= m;
 }
 m 
= d[x] - d[y];
 k 
= 0;
 
while (m)
 
//将x的深度调到和y的深度一样
 {
  
if (m&1)
   x 
= p[x][k];
  m 
>>= 1;
  k
++;
 }
 
if (x == y)return x;
 k 
= 0;
 
// 向上调节,找最近公共祖先, 算法的核心,相当于一个二分查找。
 while (x != y)
 {
  
if (p[x][k] != p[y][k] || p[x][k] == p[y][k] && k == 0)
  
//如果p[x][k]还不相等,说明节点p[x][k]还在所求点的下面,所以继续向上调节
  
//如果相等了,并且就是他们父节点,则那个节点一定就是所求点。
  {
   x 
= p[x][k];
   y 
= p[y][k];
   k
++;
  }
  
else//如果p[x][k] = p[y][k],可以说明p[x][k]一定是x和y的共祖先,但不一定是最近的。
   
//所以向下找看还有没有更近的公共祖先
  {
   k
--;
  }
 }
 
return x;
}

int main()
{
 
int i, n, m, x, y;
 
while (cin >> n >> m)
 {
  memset(head, 
0sizeof(head));
  memset(p, 
0sizeof(p));
  memset(d, 
0sizeof(d));
  cnt 
= 1;
  
for (i = 2; i <= n; i++)
  {
   scanf(
"%d"&x);
   add(x, i);
  }

  dfs(
1);
  
for (i = 0; i < m; i++)
  {
   scanf(
"%d%d"&x, &y);
   printf(
"%d\n", find_lca(x, y));
  }
 }
 
return 0;
}
 

posted on 2011-03-24 15:05 CodeStream 阅读(205) 评论(0)  编辑 收藏 引用 所属分类: acm_LCA

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理