洛谷3379
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=500010,inf=1e9; 5 int n,m,x,y,root,tot,dep[maxn],son[maxn],size[maxn],fa[maxn],top[maxn],last[maxn]; 6 struct edge{int to,pre;}e[maxn<<1]; 7 inline void read(int &k){ 8 k=0; int f=1; char c=getchar(); 9 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 10 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 11 k*=f; 12 } 13 void add(int x,int y){e[++tot].to=y; e[tot].pre=last[x]; last[x]=tot;} 14 void dfs1(int x){ 15 size[x]=1; dep[x]=dep[fa[x]]+1; 16 for (int i=last[x],to;i;i=e[i].pre) 17 if ((to=e[i].to)!=fa[x]){ 18 fa[to]=x; dfs1(to); 19 size[x]+=size[to]; 20 if (size[to]>size[son[x]]) son[x]=to; 21 } 22 } 23 void dfs2(int x,int tp){ 24 top[x]=tp; 25 if (son[x]) dfs2(son[x],tp); 26 for (int i=last[x],to;i;i=e[i].pre) 27 if ((to=e[i].to)!=fa[x]&&to!=son[x]) dfs2(to,to); 28 } 29 int lca(int x,int y){ 30 int f1=top[x],f2=top[y]; 31 while(f1!=f2){ 32 if (dep[f1]<dep[f2]) swap(x,y),swap(f1,f2); 33 x=fa[f1]; f1=top[x]; 34 } 35 return dep[x]<dep[y]?x:y; 36 } 37 int main(){ 38 read(n); read(m); read(root); 39 for (int i=1;i<n;i++) read(x),read(y),add(x,y),add(y,x); 40 dfs1(root); dfs2(root,root); 41 for (int i=1;i<=m;i++) read(x),read(y),printf("%d ",lca(x,y)); 42 return 0; 43 }