本例 求树上两点的距离
#include <bits/stdc++.h> using namespace std ; const int N=5*1e6+2,M=5*N; int nxt[M],hd[N],all,go[M],n; int dep[N],f[N][22]; void add(int x,int y){ go[++all]=y,nxt[all]=hd[x],hd[x]=all; } void init(int x,int fa){ int i,y; dep[x]=dep[fa]+1; f[x][0]=fa; for(i=0;i<=19;i++) f[x][i+1]=f[f[x][i]][i]; for(i=hd[x];i;i=nxt[i]){ y=go[i]; if(y==fa) continue; init(y,x); } } int lca(int x,int y){ int i; if(dep[x]<dep[y]) swap(x,y); for(i=19;i>=0;i--){ if(dep[f[x][i]]>=dep[y]) x=f[x][i]; } if(x==y) return x; for(i=19;i>=0;i--){ if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; } return f[x][0]; } signed main(){ int i,m,x,y,z,s; cin>>n>>m>>s; for(i=1;i<n;i++) cin>>x>>y,add(x,y),add(y,x); init(s,0); while(m--) cin>>x>>y,cout<<lca(x,y)<<endl; }
原文链接: https://www.cnblogs.com/towboa/p/17129930.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/318745
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!