這里用的是倍增。 思路是先預處理出兩個點的深度，和父節點，以及上面的祖先； 然后先跳到同一深度，看是否跳到同一點，如果是則lca是較淺的點； 否則再跳，每次2的k次方，直到最淺的 層 使得兩個點的父親相同， 這是返回他倆的父節點； 看代碼；
#include<iostream>#include<cstdio>#include<cmath>using namespace std;int n,m,s;int anc[500010][20],deep[500010];struct E{ int to,next;}tree[1000010];int last[500010],cnt;void build(int u,int v){ tree[++cnt].to=v;tree[cnt].next=last[u]; last[u]=cnt;}void swap(int &a,int &b){ int t=a;a=b;b=t;}void dfs(int now,int fa) //處理出深度和父親 { for(int i=last[now];i;i=tree[i].next) { if(tree[i].to!=fa){ deep[tree[i].to]=deep[now]+1; dfs(tree[i].to,now); anc[tree[i].to][0]=now; } }}void ready() //處理出各路祖先{ for(int j=1;(1<<j)<=n;++j) for(int i=1;i<=n;++i) anc[i][j]=anc[anc[i][j-1]][j-1];//原理是爺爺是爸爸的爸爸}int lca(int x,int y){ if(deep[x]<deep[y])swap(x,y);//默認x深，否則交換，方便處理 int maxlog=log(n)/log(2); for(int i=maxlog;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) x=anc[x][i]; //判斷看能否直接返回 if(x==y)return x; for(int i=maxlog;i>=0;i--) if(anc[x][i]!=anc[y][i]) {x=anc[x][i];y=anc[y][i]; } return anc[x][0];//返回父親}int main(){ //freopen("in.txt","r",stdin); scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n-1;++i) { int u,v; scanf("%d%d",&u,&v); build(u,v); build(v,u); } dfs(s,s); ready(); anc[s][0]=s; for(int i=1;i<=m;++i) { int a,b; scanf("%d%d",&a,&b); int ans=lca(a,b);新聞熱點
疑難解答
