本文主要是介绍poj1330（LCA最近公共祖先），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：求最近公共祖先思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。
代码如下：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<string>
#include<vector>#define N 10005
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 10e-6using namespace std;
struct node
{int v,next;
}edge[N];
int tot,head[N],d[N];
void addedge(int u,int v)
{edge[tot].next = head[u];edge[tot].v = v;head[u] = tot++;
}
int fa[N],dep[N];//son[N],siz[N],
void dfs1(int u,int pa,int depth)
{// siz[u] = 1;// son[u] = 0;fa[u] = pa;dep[u] = depth;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;dfs1(v,u,depth+1);// if(siz[v] > siz[ son[u] ]) son[u] = v;// siz[u] += siz[v];}
}
int find(int x,int y)
{while(x != y){if(dep[x] < dep[y]) swap(x,y);x = fa[x];}return x;
}int main()
{int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);memset(head,-1,sizeof(head));memset(d,0,sizeof(d));tot = 0;for(int i = 1; i < n; i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);d[v]++;}int i;for(i = 1; i <= n; i++)if(d[i] == 0) break;dfs1(i,0,1);int x,y;scanf("%d%d",&x,&y);printf("%d\n",find(x,y));}return 0;
}
这篇关于poj1330（LCA最近公共祖先）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
