题目大意：就是叫你求最近公共祖先。
最近刚学了倍增，于是用这道模板题来练练。
有人说倍增写法要读入优化，要卡常，然而经过我的测试，发现并不需要（尽管我加了读优，比原来的要快400+ms）。
C++ Code：
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
int n,m,s;
int head[1000005],next[1000005],to[1000005],cnt=0,deep[500005],p[500005][20];
void addedge(int x,int y){
cnt++;
to[cnt]=y;
next[cnt]=head[x];
head[x]=cnt;
cnt++;
to[cnt]=x;
next[cnt]=head[y];
head[y]=cnt;
}
void dfs(int u){
for(int i=head[u];i;i=next[i])
if(!deep[to[i]]){
deep[to[i]]=deep[u]+1;
p[to[i]][0]=u;
dfs(to[i]);
}
}
void init(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int x,int y){
int i;
if(deep[x]<deep[y])x^=y,y^=x,x^=y;
for(i=0;(1<<i)<=deep[x];i++);i--;
for(int j=i;j>=0;j--)
if(deep[p[x][j]]>=deep[y])x=p[x][j];
if(x==y)return x;
for(int j=i;j>=0;j--)
if(p[x][j]!=-1&&p[x][j]!=p[y][j])x=p[x][j],y=p[y][j];
return p[x][0];
}
#define C c=getchar()
int readint(){
int C;
while(!isdigit(c))C;
int p=0;
while(isdigit(c)){
p=p*10+c-'0';
C;
}
return p;
}
int main(){
n=readint(),m=readint(),s=readint();
memset(p,-1,sizeof(p));
for(int i=1;i<n;i++)addedge(readint(),readint());
deep[s]=1;
dfs(s);
init();
while(m--)printf("%d
",lca(readint(),readint()));
return 0;
}
另外附上以前写的Tarjan，比倍增快了1000+ms（尽管我也不相信倍增比Tarjan慢，然而事实就是这样）。
C++ Code：
#include<cstdio>
#include<cstring>
#include<vector>
#include<cctype>
using namespace std;
int n,m,ne=0,nq=0;
bool vis[500001],instack[500001];
int f[500001],head[500001],que[500001],ans[500001];
struct query{
int same,next,to,num;
bool flag;
}q[1000001];
struct edge{
int to,next;
}e[1000001];
void add_edge(int x,int y){
e[++ne].to=y;
e[ne].next=head[x];
head[x]=ne;
e[++ne].to=x;
e[ne].next=head[y];
head[y]=ne;
}
void add_que(int x,int y,int z){
q[++nq].to=y;
q[nq].same=nq+1;
q[nq].num=z;
q[nq].next=que[x];
que[x]=nq;
q[++nq].to=x;
q[nq].same=nq-1;
q[nq].num=z;
q[nq].next=que[y];
que[y]=nq;
}
int find(int x){
if(f[x]==x)return x;
return f[x]=find(f[x]);
}
void tarjan(int root){
instack[root]=true;
for(int i=head[root];i;i=e[i].next){
int v=e[i].to;
if(instack[v])continue;
tarjan(v);
f[v]=root;
vis[v]=true;
}
for(int i=que[root];i;i=q[i].next)
if(vis[q[i].to]&&!q[i].flag){
ans[q[i].num]=find(q[i].to);
q[i].flag=q[q[i].same].flag=true;
}
instack[root]=false;
}
#define C c=getchar()
int readint(){
char C;
while(!isdigit(c))C;
int d=0;
while(isdigit(c)){
d=d*10+c-'0';
C;
}
return d;
}
int main(){
int t;
n=readint(),m=readint(),t=readint();
memset(vis,0,sizeof(vis));
memset(instack,0,sizeof instack);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<n;i++){
int u=readint(),v=readint();
add_edge(u,v);
}
for(int i=1;i<=m;i++){
int x=readint(),y=readint();
add_que(x,y,i);
}
tarjan(t);
for(int i=1;i<=m;i++)
printf("%d
",ans[i]);
return 0;
}
----------------------------------------------------------2017.7.13----------------------------------------------------------
最近学了树链剖分，于是用树剖写了个LCA，不过速度居然没有Tarjan快。
C++ Code:
#include<cstdio>
#include<cctype>
#include<algorithm>
using std::swap;
#define C c=getchar()
int n,m,s;
int head[500005],next[1000005],cnt=0,to[1000005],deep[500005],fa[500005],sz[500005],top[500005];
inline int readint(){
char C;
while(!isdigit(c))C;
int p=0;
while(isdigit(c))p=p*10+c-'0',C;
return p;
}
inline void addedge(int u,int v){
to[++cnt]=v;
next[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
next[cnt]=head[v];
head[v]=cnt;
}
void dfs(int x){
deep[x]=deep[fa[x]]+1;
sz[x]=1;
for(int i=head[x];i;i=next[i])
if(fa[x]!=to[i]){
fa[to[i]]=x;
dfs(to[i]);
sz[x]+=sz[to[i]];
}
}
void dfs2(int x){
if(!top[x])top[x]=x;
int t=0;
for(int i=head[x];i;i=next[i])
if(fa[x]!=to[i]&&sz[to[i]]>sz[t])t=to[i];
if(t)top[t]=top[x],dfs2(t);
for(int i=head[x];i;i=next[i])
if(fa[x]!=to[i]&&to[i]!=t)dfs2(to[i]);
}
int query(int x,int y){
for(;top[x]!=top[y];x=fa[top[x]])
if(deep[top[x]]<deep[top[y]])swap(x,y);
return deep[x]<deep[y]?x:y;
}
int main(){
n=readint(),m=readint(),s=readint();
for(int i=1;i<n;++i)addedge(readint(),readint());
dfs(s);dfs2(s);
while(m--)printf("%d
",query(readint(),readint()));
return 0;
}