OJ题号：洛谷3379
思路：树链剖分
1 #include<cstdio> 2 #include<cctype> 3 const int N=500001; 4 int n,m,s,ecount=0,head[N]={0},depth[N]={0},parent[N]={0},size[N]={0},next[N]={0},top[N]={0}; 5 struct Edge { 6 int next,to; 7 }; 8 Edge e[N<<1]; 9 void add_edge(int x,int y) { 10 e[++ecount]=(Edge){head[x],y}; 11 head[x]=ecount; 12 } 13 inline int getint() { 14 int ch; 15 while(!isdigit(ch=getchar())); 16 int x=ch^'0'; 17 while(isdigit(ch=getchar())) x=((x+(x<<2))<<1)+(ch^'0'); 18 return x; 19 } 20 void dfs1(const int x) { 21 depth[x]=depth[parent[x]]+1; 22 size[x]=1; 23 for(int i=head[x];i;i=e[i].next) { 24 if(e[i].to==parent[x]) continue; 25 if(!parent[e[i].to]) { 26 parent[e[i].to]=x; 27 dfs1(e[i].to); 28 size[x]+=size[e[i].to]; 29 if(size[next[x]]<size[e[i].to]) { 30 next[x]=e[i].to; 31 } 32 } 33 } 34 } 35 void dfs2(const int x) { 36 top[x]=(x==next[parent[x]])?top[parent[x]]:x; 37 for(int i=head[x];i;i=e[i].next) { 38 if(parent[e[i].to]==x) { 39 dfs2(e[i].to); 40 } 41 } 42 } 43 inline void swap(int &x,int &y) { 44 int t; 45 t=x; 46 x=y; 47 y=t; 48 } 49 inline int lca(int x,int y) { 50 while(top[x]!=top[y]) { 51 if(depth[top[x]]<depth[top[y]]) { 52 swap(x,y); 53 } 54 x=parent[top[x]]; 55 } 56 return (depth[x]<depth[y])?x:y; 57 } 58 int main() { 59 n=getint();m=getint();s=getint(); 60 while(--n) { 61 int a=getint(),b=getint(); 62 add_edge(a,b); 63 add_edge(b,a); 64 } 65 dfs1(s); 66 dfs2(s); 67 while(m--) { 68 int x=getint(),y=getint(); 69 printf("%d ",lca(x,y)); 70 } 71 return 0; 72 }