为什么我也是错的??我也开了两倍啊??
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
int n,m,size,s,x,y,u,v,tot;
int next[1000005],head[1000005],fa[1000005],d[1000005],f[1000005][21],vet[1000005];
bool vis[1000005];
int read(){
int re=0;
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){
re=re*10+ch-'0';
ch=getchar();
}
return re;
}
inline void add(int u,int v)
{
size++;
next[size]=head[u];
head[u]=size;
vet[size]=v;
}
void dfs(int root,int depth)
{
d[root]=depth;vis[root]=1;
for (int i=head[root];i!=0;i=next[i])
{
if (vis[vet[i]]!=0) continue;
fa[vet[i]]=root;
dfs(vet[i],depth+1);
}
}
inline int lca(int u,int v)
{
if (d[u]<d[v]) swap(u,v);
for(int i=0;i<=20;i++) if (((d[u]-d[v])>>i)&1!=0) u=f[u][i];
for (int i=20;i>=0;i--)
if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
if (u==v) return u;else return fa[u];
}
int main()
{
n=read();m=read();s=read();
for (int i=1;i<n;i++) {
x=read();y=read();
add(x,y);add(y,x);
}
dfs(s,0);
for(int i=1;i<=n;i++) f[i][0]=fa[i];
for (int j=1;1<<j<=n;j++)
for(int i=1;i<=n;i++)
f[i][j]=f[f[i][j-1]][j-1];
for (int i=1;i<=m;i++)
{
u=read();v=read();
cout << lca(u,v) << endl;
}
return 0;
}
```
by zhou_yk @ 2018-07-22 14:25:56