洛谷3379 最近公共祖先模板（倍增）

#include<iostream> #include<cstdio> #include<cstring> #define maxn 500010 #define S 21 using namespace std; int deep[maxn],head[maxn],p1,p2,n,m,num,ans,s,x,y,fa[maxn][S+5]; struct node { int from; int to; int next; }e[maxn*2]; void add(int from,int to) { e[++num].from=from; e[num].to=to; e[num].next=head[from]; head[from]=num; } int init() { int x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void swap(int &a,int &b) { int t=a;a=b;b=t; } void get_fa() { for(int j=1;j<=S;j++) for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } void Dfs(int now,int from,int c) { fa[now][0]=from; deep[now]=c; for(int i=head[now];i;i=e[i].next) { int v=e[i].to; if(v!=from) Dfs(v,now,c+1); } } int get_same(int a,int t) { for(int i=0;i<S;i++) if(t&(1<<i)) a=fa[a][i]; return a; } int LCA(int a,int b) { if(deep[a]<deep[b]) swap(a,b); a=get_same(a,deep[a]-deep[b]); if(a==b) return a; for(int i=S;i>=0;i--) { if(fa[a][i]!=fa[b][i]) { a=fa[a][i]; b=fa[b][i]; } } return fa[a][0]; } int main() { n=init();m=init();s=init(); int x,y; for(int i=1;i<n;i++) { x=init();y=init(); add(x,y); add(y,x); } Dfs(s,s,0); get_fa(); for(int i=1;i<=m;i++) { p1=init();p2=init(); int ans=LCA(p1,p2); printf("%d\n",ans); } return 0; }