求最近公共祖先的三种方法(LCA)
书P375~380
以下规定:n为树的点数,m为询问次数
以下程序的模版题:http://acm.hdu.edu.cn/showproblem.php?pid=2586
例题:https://ac.nowcoder.com/acm/contest/1065/1009
①向上标记法
时间复杂度O(nm)
②树上倍增法
设f[x,k]为x的第2^k辈祖先,则f[x,0]就是x的父节点
f[x,k]=f[f[x,k-1],k-1]
时间复杂度O((n+m) log n)
#include using namespace std; const int maxn=50000+1; int f[maxn][20],d[maxn],dist[maxn]; int ver[2*maxn],Next[2*maxn],edge[2*maxn],head[maxn]; int T,n,m,tot,t; queue q; void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; Next[tot]=head[x]; head[x]=tot; } void bfs() { q.push(1); d[1]=1; while(q.size()) { int x=q.front(); q.pop(); for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(d[y]) { continue; } d[y]=d[x]+1; dist[y]=dist[x]+edge[i]; f[y][0]=x; for(int j=1;j<=t;j++) { f[y][j]=f[f[y][j-1]][j-1]; } q.push(y); } } } int lca(int x,int y) { if(d[x]>d[y]) { swap(x,y); } for(int i=t;i>=0;i--) { if(d[f[y][i]]>=d[x]) { y=f[y][i]; } } if(x==y) { return x; } for(int i=t;i>=0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } int main() { cin>>T; while(T--) { cin>>n>>m; t=(int)(log(n)/log(2))+1; for(int i=1;i<=n;i++) { head[i]=d[i]=0; } tot=0; for(int i=1;i<=n-1;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z);add(y,x,z); } bfs(); for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; cout<<dist[x]+dist[y]-2*dist[lca(x,y)]<<endl; } } return 0; }
③Tarjan算法
时间复杂度O(n+m)
#include using namespace std; const int maxn=50000+1; int ver[2*maxn],Next[2*maxn],edge[2*maxn],head[2*maxn]; int fa[maxn],d[maxn],v[maxn],lca[maxn],ans[maxn]; vector query[maxn],query_id[maxn]; int T,n,m,tot,t; void add(int x,int y,int z) { ver[++tot]=y; edge[tot]=z; Next[tot]=head[x]; head[x]=tot; } void add_query(int x,int y,int id) { query[x].push_back(y),query_id[x].push_back(id); query[y].push_back(x),query_id[y].push_back(id); } int get(int x) { if(x==fa[x]) { return x; } return fa[x]=get(fa[x]); } void tarjan(int x) { v[x]=1; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if(v[y]) { continue; } d[y]=d[x]+edge[i]; tarjan(y); fa[y]=x; } for(int i=0;i<query[x].size();i++) { int y=query[x][i],id=query_id[x][i]; if(v[y]==2) { int lca=get(y); ans[id]=min(ans[id],d[x]+d[y]-2*d[lca]); } } v[x]=2; } int main() { cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) { head[i]=0;fa[i]=i;v[i]=0; query[i].clear();query_id[i].clear(); } tot=0; for(int i=1;i<=n-1;i++) { int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } for(int i=1;i<=m;i++) { int x,y; cin>>x>>y; if(x==y) { ans[i]=0; } else { add_query(x,y,i); ans[i]=1<<30; } } tarjan(1); for(int i=1;i<=m;i++) { cout<<ans[i]<<endl; } } return 0; }
参考文章:https://blog.csdn.net/qq_45432665/article/details/106038095
#笔试题目#