LCA模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<algorithm>
 8 using namespace std;
 9 #define MAXN 100010
10 struct node{int y,next;}e[MAXN*2];
11 int n,m,len,Link[MAXN],deep[MAXN],f[MAXN],anc[MAXN][25];
12 inline int read()
13 {
14     int x=0,f=1;  char ch=getchar();
15     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}
16     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}
17     return x*f;
18 }
19 void insert(int x,int y)  {e[++len].next=Link[x];Link[x]=len;e[len].y=y;}
20 void dfs(int x,int fa)
21 {
22     anc[x][0]=f[x];
23     for(int i=1;i<=20;i++)  anc[x][i]=anc[anc[x][i-1]][i-1];
24     for(int i=Link[x];i;i=e[i].next)
25         if(e[i].y!=fa)
26         {
27             f[e[i].y]=x;
28             deep[e[i].y]=deep[x]+1;
29             dfs(e[i].y,x);
30         }
31 }
32 int lca(int x,int y)
33 {
34     if(deep[x]<deep[y])  swap(x,y);
35     for(int i=20;i>=0;i--)
36         if(deep[anc[x][i]]>=deep[y])  x=anc[x][i];
37     if(x==y)  return x;
38     for(int i=20;i>=0;i--)
39         if(anc[x][i]!=anc[y][i])  x=anc[x][i],y=anc[y][i];
40     return f[x];
41 }
42 int main()
43 {
44     //freopen("cin.in","r",stdin);
45     //freopen("cout.out","w",stdout);
46     n=read();  m=read();
47     for(int i=1;i<n;i++)  {int x=read(),y=read();  insert(x,y);  insert(y,x);}
48     deep[1]=1;  dfs(1,0);
49     for(int i=1;i<=m;i++)
50     {
51         int x=read(),y=read();
52         printf("%d\n",lca(x,y));
53     }
54     return 0;
55 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<ctime>
 8 using namespace std;
 9 struct node{int y,next;}e[201000];
10 int n,m,len,z,a[201000],dep[201000],f[201000],top[201000],son[201000],size[201000];
11 inline int read()
12 {
13     int x=0,f=1;  char ch=getchar();
14     while(!isdigit(ch))  {if(ch==‘-‘)  f=-1;  ch=getchar();}
15     while(isdigit(ch))  {x=x*10+ch-‘0‘;  ch=getchar();}
16     return x*f;
17 }
18 void insert(int xx,int yy)
19 {
20     e[++len].next=a[xx];
21     a[xx]=len;
22     e[len].y=yy;
23 }
24 void dfs1(int x)
25 {
26     dep[x]=dep[f[x]]+1;  size[x]=1;
27     for(int i=a[x];i;i=e[i].next)
28     {
29         if(e[i].y!=f[x]&&!f[e[i].y])
30         {
31             f[e[i].y]=x;
32             dfs1(e[i].y);
33             size[x]+=size[e[i].y];
34             if(size[son[x]]<size[e[i].y])  son[x]=e[i].y;
35         }
36     }
37 }
38 void dfs2(int x)
39 {
40     if(x==son[f[x]])  top[x]=top[f[x]];
41     else top[x]=x;
42     for(int i=a[x];i;i=e[i].next)  
43         if(f[e[i].y]==x)  dfs2(e[i].y);
44 }
45 int ask(int xx,int yy)
46 {
47     while(top[xx]!=top[yy])
48     {
49         if(dep[top[xx]]>dep[top[yy]])  xx=f[top[xx]];
50         else yy=f[top[yy]];
51     }
52     if(dep[xx]<dep[yy])  return xx;
53     else return yy;
54 }
55 int main()
56 {
57     n=read();  m=read();
58     for(int i=1;i<n;i++)
59     {
60         int xx=read(),yy=read();
61         insert(xx,yy);
62         insert(yy,xx);
63     }
64     dfs1(1);
65     dfs2(1);
66     for(int i=1;i<=m;i++)
67     {
68         int xx=read(),yy=read();
69         printf("%d\n",ask(xx,yy));
70     }
71     return 0;
72 }