7 条题解
-
11
本题的核心思路：倍增。 如果暴力求LCA，要从两个节点开始，一步一步往根节点方向走，记录路径，再从路径最后（就是根节点）开始比较，比较什么时候后出现不同。代码如下：
#include<bits/stdc++.h> using namespace std; const int MAXN=500000+5; const int MAXM=500000+5; int head[MAXN]; int father[MAXN]; bool visited[MAXM]; int bianshu; struct edge { int v,next; }g[2*MAXM]; void addedge(int u,int v) { g[++bianshu].next=head[u]; g[bianshu].v=v; head[u]=bianshu; return; } queue <int> q; int s; void bfs() { q.push(s); while(!q.empty()) { int ppp=q.front(); q.pop(); for(int i=head[ppp];i;i=g[i].next) { if(!visited[g[i].v]) { visited[g[i].v]=true; father[g[i].v]=ppp; q.push(g[i].v); } } } } int path1[MAXN]; int path2[MAXN]; int cntp1,cntp2; int ans; int main() { int n,q; int uu,vv; int a,b; int LCA,a1,a2; scanf("%d%d%d",&n,&q,&s); for(int i=1;i<=n-1;++i) { scanf("%d%d",&uu,&vv); addedge(uu,vv); addedge(vv,uu); } father[s]=s; visited[s]=true; bfs(); for(int i=1;i<=q;++i) { scanf("%d%d",&a,&b); for(int j=a;j!=s;j=father[j]) { path1[++cntp1]=j; } path1[++cntp1]=s; for(int j=b;j!=s;j=father[j]) { path2[++cntp2]=j; } path2[++cntp2]=s; while(path1[cntp1--]==path2[cntp2--]) { ans=path1[cntp1+1]; } printf("%d\n",ans); memset(path1,0,sizeof(path1)); memset(path2,0,sizeof(path2)); cntp1=0; cntp2=0; ans=0; } return 0; }然而，暴力的时间和空间复杂度根本无法接受。 我们来思考下面这个问题：我为什么要一个一个跳到根节点呢？ 于是乎，“倍增”就出现了。 定义jump[a][b]数组的意义如下： 编号为a的点往根节点方向走(2^b)次之后的点的编号。 每一次不需要一个一个往根节点方向走，而是采取了一种类似于跳跃的模式。 往根节点方向走（2^0)次，即得到这个点的父亲节点。所以先初始化数组：
for(int i=1;i<=n;++i) { jump[i][0]=father[i]; }//jump初值然后，再将jump[i][1] jump[i][2]等求出来。 jump[i][j]可以通过jump[i][j-1]再往根节点方向走j-1次得到。 推得状态转移方程：jump[i][j]=jump[jump[i][j-1]][j-1];
for(int j=1;j<=30;++j) { for(int i=1;i<=n;++i) { jump[i][j]=jump[jump[i][j-1]][j-1]; } }//初始化jump数组接下来我们要开始求最近公共祖先了。然而，如果节点a深度为16，节点b深度为32，所求得的跳跃次数、路径长度都是不一样的，我们又要记录路径然后从后往前比较。 于是乎，我们想了一个办法：先把a，b跳跃到同一深度，再进行剩下的跳跃。（有更简便写法）
if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 { for(int k=30;k>=0;--k) { if(tmp>=(1<<k)) { a=jump[a][k]; } } } else if(dep[b]>dep[a]) { for(int k=30;k>=0;--k) { if(tmp>=(1<<k)) { b=jump[b][k]; } } }//使得a,b位于同一深度如果这个时候已经跳到同一个点，即a==b，则直接输出，否则进行我们最后的跳跃。只要jump[i][k]!=jump[j][k]（k取值可以不做限制，因为无意义的那些范围的jump值均会是0）我们就跳跃。跳跃完之后，你会惊奇的发现father[a]==father[b];（可以自己模拟一下）所以我们输出任意一边的father均可。 一些没提到的细节和代码如下：
#include<bits/stdc++.h> using namespace std; const int MAXN=500000+5; const int MAXM=1000000+5; int head[MAXN];//链式前向星 int father[MAXN];//父亲节点 bool visited[MAXN]; int bianshu; struct edge//链式前向星 { int v,next; }g[2*MAXM];//双向边，记得开2倍范围 void addedge(int u,int v)//链式前向星无权值加边 { g[++bianshu].next=head[u]; g[bianshu].v=v; head[u]=bianshu; return; } queue <int> q;//bfs用 int dep[MAXN];//每个点的深度 void bfs(int s,int depth)//求father { q.push(s); dep[s]=depth; while(!q.empty()) { int ppp=q.front(); q.pop(); for(int i=head[ppp];i;i=g[i].next)//遍历 { if(!visited[g[i].v]) { visited[g[i].v]=true; father[g[i].v]=ppp; dep[g[i].v]=dep[ppp]+1;//存储深度，比父亲节点深度大1 q.push(g[i].v); } } } } int jump[MAXN][35];//定义：j[a][b]为a号点往根节点方向走(1<<b)次后的节点编号 int main() { int n,q,s; int uu,vv; int a,b; int tmp;//深度差 scanf("%d%d",&n,&q);//有时候需要读入s s=1; for(int i=1;i<=n-1;++i) { scanf("%d%d",&uu,&vv); addedge(uu,vv); addedge(vv,uu); }//加边 father[s]=0;//注意：father[根]一定要设为0，否则后面跳跃时出问题 visited[s]=true; bfs(s,1);//求father数组 for(int i=1;i<=n;++i) { jump[i][0]=father[i]; }//jump初值 for(int j=1;j<=30;++j) { for(int i=1;i<=n;++i) { jump[i][j]=jump[jump[i][j-1]][j-1]; } }//初始化jump数组 while(q--)//操作 { scanf("%d%d",&a,&b); tmp=(dep[a]>dep[b]?dep[a]-dep[b]:dep[b]-dep[a]);//深度差值 if(dep[a]>dep[b]) //每次判断是否跳跃(1<<k)次，跳跃到同一深度 { for(int k=30;k>=0;--k) { if(tmp>=(1<<k)) { a=jump[a][k]; tmp-=(1<<k); } } } else if(dep[b]>dep[a]) { for(int k=30;k>=0;--k) { if(tmp>=(1<<k)) { b=jump[b][k]; tmp-=(1<<k); } } }//使得a,b位于同一深度 if(a==b)//跳到同一个点，即LCA就是当前的点，需要特判。 { printf("%d\n",a); continue; } for(int k=30;k>=0;--k) { if((jump[a][k]^jump[b][k]))//异或符号^在此处等价于！= 符号 { a=jump[a][k]; b=jump[b][k]; } }//跳2的k次方次 printf("%d\n",father[a]); } return 0; }感谢阅读我这一篇又臭又长的题解。
-
Whisperain @ 2021-10-15 20:59:27
好像有一句写错了 求jump[i][1] jump[i][2]的时候 jump[i][j]是要通过jump[i][j-1]再往根节点方向走次得到
-
就是说2的j-1次方 次
-
王靖翔
@ 2023-10-17 20:07:21
%%%
-
-
4
tg重点知识点：LCA
求LCA的基本方式：
- 在线法
代表：倍增，rmq
这里介绍倍增法。
先预处理出每一个节点的 级祖先以及深度。
求LCA时，先让两个节点深度相同，再从大到小枚举 ，如果 的 级祖先不等于 的 级祖先就往上跳。
因为我们跳的是LCA的下一层，所以要输出 的 级祖先。
核心代码：
vector<int> g[500001]; int n,q; int depth[500001],f[500001][31]; void dfs(int x, int fa) { depth[x]=depth[fa]+1; f[x][0]=fa; For(i,1,log2(depth[x])+1) f[x][i]=f[f[x][i-1]][i-1]; For(i,0,g[x].size()-1) if(g[x][i]!=fa) dfs(g[x][i],x); } int lca(int x, int y) { if(depth[y]<depth[x]) swap(y,x); while(depth[y]>depth[x]) y=f[y][(int)log2(depth[y]-depth[x])]; if(x==y) return x; ForDown(k,log2(depth[y]),0) { if(f[x][k]!=f[y][k]) { x=f[x][k],y=f[y][k]; } } return f[x][0]; } signed main() { read(n,q); For(i,1,n-1) { int u,v; read(u,v); g[u].push_back(v); g[v].push_back(u); } dfs(1,1); //cout<<"wedrftgyhujikoswerdtfyguh"<<endl; while(q--) { int x,y; read(x,y); write_with_endl(lca(x,y)); } return 0; }复杂度
- 离线法
代表：tarjan
把所有询问存下来，然后在回溯时将并查集中当前节点的“父亲”设为它的父节点。然后如果有一个询问的两个点都算过了，从并查集中找结果存进来。最后输出。
核心代码：
int n,m,s; struct Edge { int v,nxt; }query[1000001]; int head[500001],cnt=0; vector<int> g[500001]; int lca[1000001]; void add(int x, int y) { query[++cnt]=(Edge){y,head[x]}; head[x]=cnt; } bool used[500001]; int f[500001]; int find(int x) { return f[x]==x ? f[x] : f[x]=find(f[x]); } void tarjan(int x) { used[x]=1; For(i,0,g[x].size()-1) { if(used[g[x][i]]) continue; tarjan(g[x][i]); f[g[x][i]]=x; } for(int i=head[x];i;i=query[i].nxt) { if(used[query[i].v]) { lca[i%2+i]=find(query[i].v); } } } int main() { read(n);read(m);read(s); For(i,1,n) f[i]=i; For(i,1,n-1) { int u,v; read(u);read(v); g[u].push_back(v); g[v].push_back(u); } For(i,1,m) { int u,v; read(u);read(v); add(u,v); add(v,u); } tarjan(s); For(i,1,m) { write(lca[2*i]); putchar('\n'); } return0; }复杂度 。
-
2
来点不一样的，用树链剖分求
LCA。 先把树剖成链，记录每个点所在链的最顶端节点 ， 每次往上跳即可。#include <bits/stdc++.h> using namespace std; /*********************** Author : ACgod Date : 2022/5/21 School : Xiamen No.1 High School of Fujian ***********************/ #define reg register #define rep(i, a, b) for(register int i = a; i <= b; i ++) #define pb push_back vector<int> e[500005]; int n, q; template <class T> T read() { reg T s=0,f=1; reg char ch = getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar(); return f*s; } int maxson[500005], size[500005]; int top[500005], dep[500005]; int fat[500005]; void dfs1(int u, int fa) { dep[u] = dep[fa] + 1; fat[u] = fa; int sizeofson = 0; for(int i = 0; i < e[u].size(); i ++) { int to = e[u][i]; if(to == fa) continue; dfs1(to, u); size[u] += size[to]; if(size[to] > sizeofson) { maxson[u] = to; sizeofson = size[to]; } } size[u]++; } void dfs2(int u, int topf, int fa) { top[u] = topf; for(int i = 0; i < e[u].size(); i ++) { int to = e[u][i]; if(to == fa) continue; if(maxson[u] == to) { dfs2(to, topf, u); } else dfs2(to, to, u); } } int lca(int x, int y) { if(dep[top[x]] < dep[top[y]]) swap(x, y); return top[x] == top[y] ? (dep[x] < dep[y] ? x : y ): lca(fat[top[x]], y); } int main() { n = read<int>(), q = read<int>(); rep(i, 1, n - 1) { int u, v; u = read<int>(), v = read<int>(); e[u].pb(v), e[v].pb(u); } dfs1(1, 0); dfs2(1, 1, 0); rep(i, 1, q) { int x, y; x = read<int>(), y = read<int>(); printf("%d\n", lca(x, y)); } return 0; } -
2
倍增法求 LCA 。
#include <bits/stdc++.h> using std::cin; using std::cout; using std::endl; int n, q, u, v, fa[500005][20], dep[500005]; std::vector<int> g[500005]; void bfs(int root) { memset(dep, 0x3f, sizeof(dep)); std::queue<int> q; dep[0] = 0; dep[root] = 1; q.push(root); while (!q.empty()) { int t = q.front(); q.pop(); for (int v : g[t]) { if (dep[v] > dep[t] + 1) { dep[v] = dep[t] + 1; q.push(v); fa[v][0] = t; for (int k = 1; k < 20; k++) { fa[v][k] = fa[fa[v][k - 1]][k - 1]; } } } } } int lca(int a, int b) { if (dep[a] < dep[b]) std::swap(a, b); for (int k = 19; k >= 0; k--) { if (dep[fa[a][k]] >= dep[b]) { a = fa[a][k]; } } if (a == b) return a; for (int k = 19; k >= 0; k--) { if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } } return fa[a][0]; } int main() { scanf("%d%d", &n, &q); for (int i = 1; i < n; i++) { scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } bfs(1); while (q--) { scanf("%d%d", &u, &v); printf("%d\n", lca(u, v)); } return 0; } -
-4
Karl Aurora
LV 7
@ 2022-1-22 22:11:04
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct zzz { int t, nex; }e[500010 << 1]; int head[500010], tot; void add(int x, int y) { e[++tot].t = y; e[tot].nex = head[x]; head[x] = tot; } int depth[500001], fa[500001][22], lg[500001]; void dfs(int now, int fath) { fa[now][0] = fath; depth[now] = depth[fath] + 1; for(int i = 1; i <= lg[depth[now]]; ++i) fa[now][i] = fa[fa[now][i-1]][i-1]; for(int i = head[now]; i; i = e[i].nex) if(e[i].t != fath) dfs(e[i].t, now); } int LCA(int x, int y) { if(depth[x] < depth[y]) swap(x, y); while(depth[x] > depth[y]) x = fa[x][lg[depth[x]-depth[y]] - 1]; if(x == y) return x; for(int k = lg[depth[x]] - 1; k >= 0; --k) if(fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k]; return fa[x][0]; } int main() { int n, m, s = 1; scanf("%d%d", &n, &m); for(int i = 1; i <= n-1; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } for(int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i); dfs(s, 0); for(int i = 1; i <= m; ++i) { int x, y; scanf("%d%d",&x, &y); printf("%d\n", LCA(x, y)); } return 0; } -
-6
题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式 输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例 输入 #1复制
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5 输出 #1复制
4 4 1 4 4 说明/提示 时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
该树结构如下：
第一次询问：2、4的最近公共祖先，故为4。
第二次询问：3、2的最近公共祖先，故为4。
第三次询问：3、5的最近公共祖先，故为1。
第四次询问：1、2的最近公共祖先，故为4。
第五次询问：4、5的最近公共祖先，故为4。
故输出依次为4、4、1、4、4。
做这个题之前，刚学了树链剖分，这就用上了，求最近公共祖先（LCA）其实就是用树链剖分后，进行简单的链查询即可（让那两个结点的指针中所处链的顶端结点深度小的（也就是靠下的那条链）的指针不断向上跳啊，跳啊。。。直到两指针在同一条链时返回深度较小的那个指针所指的结点编号（即为LCA）即可）。
完整代码：
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define int long long using namespace std; const int maxn=5e5+5; typedef struct Edge { int next,to; }edg; edg e[maxn<<1]; int n,m,s,cnt,head[maxn<<1];
void AddEdge(int u,int v) { e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt++; }
int fa[maxn],son[maxn],depth[maxn],siz[maxn]; void dfs1(int u,int f) { fa[u]=f; depth[u]=depth[f]+1; siz[u]=1; int maxsize=-1; for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(v==f) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>maxsize) { maxsize=siz[v]; son[u]=v; } } }
int tim,dfn[maxn],top[maxn]; void dfs2(int u,int t) { dfn[u]=++tim; top[u]=t; if(!son[u]) return; dfs2(son[u],t); for(int i=head[u];~i;i=e[i].next) { int v=e[i].to; if(vfa[u]||vson[u]) continue; dfs2(v,v); } }
int query(int x,int y) { while(top[x]!=top[y]) { if(depth[top[x]]<depth[top[y]]) swap(x,y); x=fa[top[x]]; } if(depth[x]>depth[y]) swap(x,y); return x; }
signed main() { // ios::sync_with_stdio(false); // cin.tie(0); memset(head,-1,sizeof(head)); scanf("%lld%lld%lld",&n,&m,&s); int N=n-1; while(N--) { int u,v; scanf("%lld%lld",&u,&v); AddEdge(u,v); AddEdge(v,u); } dfs1(s,s); dfs2(s,s); while(m--) { int x,y; scanf("%lld%lld",&x,&y); int ans=query(x,y); cout<<ans<<endl; } }
- 1
