最近公共祖先两种算法小结.docVIP

最近公共祖先两种算法小结 *Cyxgrtx(/) 最近公共祖先Lowest Common Ancestors，简称LCA），对于有根树T的两个结点u、v，最近公共祖先LCA(u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大，也可理解为中u到v中深度最小的点（取自百度百科） LCA常用的两种算法倍增tarjan算法（当然，还有其他算法）树上算法是一种在线算法，tarjan是离线算法（在线离线算法百度一下O(∩_∩)O~~） 倍增算法| dfs+| O(nlogn) （建议先去了解中的ST算法 我们先定义的，那么对于0]就是i的父亲节点。初步了解过算法的话，不难想到 (p.s:f[1][23]=f[ f[1][22] ][22]，第1个结点的第为第一个节点的第四个祖先的第四个祖先初始状态和动态转移方程，我们便不难求出f[n][m]） 接下来需要针对每一询问得到的需要一个dep数组表示每个结点的深度。 结点v它们的最近公共祖先在同一深度上，所以我们先u、v同一深度上。只需要深度差，只需要用二进制表示深度向上找就行了这就是倍增思想O(log n)。 如果同一深度但并不是同一个祖先，我们就需要让u、v同时，找到。循环由小到大，这样才能得到最近的公共祖先。 //CodeVs 1036 #includecstdlib #includecstdio #includecstring #includealgorithm #includecmath #define For1(x, y) for(int i=x; i=y; i++) #define LFor(x, y) for(linklist *j=y[x].next; j; j=j-next) #define For2(x, y) for(int i=x; i=y; i--) #define N 30100 #define M 17 using namespace std; int n,m; struct linklist{int s, val; linklist *next;}; linklist t[N]; int dep[N]; int f[N][M]; int vis[N]; int dis[N]; void insert(linklist x, int y, int val) { linklist *t=new(linklist); t-next=x.next;t-val=val; t-s=y;x.next=t; } void dfs(int x, int d) { vis[x]=1;dep[x]=d; LFor(x,t){ if (!vis[j-s]) { dis[j-s]=dis[x]+j-val; dfs(j-s, d+1); f[j-s][0]=x; } } } void ST() { for(int j=1; jM; j++) For1(1,n) f[i][j]=f[f[i][j-1]][j-1]; } void init() { memset(vis, 0, sizeof(vis)); memset(dep, 0, sizeof(dep)); memset(dis, 0, sizeof(dis)); scanf(%d, n); For1(1,n-1) { int x, y,val; scanf(%d %d, x, y); insert(t[x], y, 1);insert(t[y],x, 1); } dfs(1,1); ST(); } void swap(int x, int y){x=x^y;y=x^y;x=x^y;} int Lca(int u, int v) { if (dep[u]dep[v]) swap(u,v); int d=dep[u]-dep[v]; For2(M-1,0) if ((1i)d) u=f[u][i],printf(%d %d\n, i, u); if (u==v) return u; For2(M-1,0) if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i]; return f[u][0]; } void query() { int x,y; int ans=0; scanf(%d, m); scanf(%d, x); For1(2,m){ scanf(%d, y); if (x!=y) { ans+=dis[x]+dis[y]-2*dis[Lca(x,y)]; } x=y; } printf(%d, ans); } int mai