luogu P3379 【模板】最近公共祖先（LCA）
luoguP3379【模板】最近公共祖先（LCA）
最近公共祖先：是指在有根树中，找出某两个结点u和v最近的公共祖先。
对于有根树T的两个结点u、v，运用二进制拆分
1.将u，v中深度较深的那一个点向上走到和深度较浅的点
2.两个点一起向上走，直到走到同一个点时 u， v 的爸爸相同，这个点就是u，v的最近公共祖先，记作LCA（u，v）
p[ j ][ i ] = 由编号 j 的点向上走 2^i 步到达点的编号
状态转移公式
p[j][i]=p[p[j][i-1]][i-1]
向上走 2^i 步到达p[ j ][ i ]==先走2^（i-1）到达p[ j ][ i - 1 ]再走2^（i-1）到达p[p [ j ] [ i-1 ]] [ i-1 ]
#include<cstdio> #include<iostream> using namespace std; int n,m,s,k; const int maxn=500005*2; int head[maxn],to[maxn],nxt[maxn],dep[maxn],p[maxn][30]; int log(int x) { int a=1,sum=0; while(x>=a) { a*=2; sum++; } return sum; } void add(int x,int y) { k++; nxt[k]=head[x]; to[k]=y; head[x]=k; } void dfs(int x,int fa) { for(int i=head[x];i;i=nxt[i]) { if(to[i]==fa) continue; dep[to[i]]=dep[x]+1; p[to[i]][0]=x; dfs(to[i],x); } return ; } void lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=k;i>=0;i--) { if(dep[p[x][i]]>=dep[y]) x=p[x][i]; if(dep[p[x][i]]==dep[y]) break; } if(x==y) { printf("%d\n",x); return; } for(int i=k;i>=0;i--) { if(p[x][i]!=p[y][i]) { x=p[x][i]; y=p[y][i]; } } printf("%d\n",p[x][0]); return; } int main() { int a,b; scanf("%d%d%d",&n,&m,&s); dep[s]=1; p[s][0]=s; for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } dfs(s,0); k=log(n)/log(2)+1; for(int i=1;i<=k;i++) for(int j=1;j<=n;j++) p[j][i]=p[p[j][i-1]][i-1]; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); lca(a,b); } return 0; }优质内容筛选与推荐>>
1、ch6 列表和导航条
2、使用vcenter安装虚拟机
3、Jquery Easy UI要导入的js文件
4、CamlQuery对SharePointOnline List 发起查询请求
5、Unity3D历史版本下载列表