每次输出跳到哪个节点了自己调啊。。
by SSerxhs @ 2019-02-16 22:38:35
您都知道是这么一小段的问题了
by SSerxhs @ 2019-02-16 22:38:48
@[Dark_Van](/space/show?uid=112720)
```cpp
inline int LCA(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);//让u的深度更大
for(register int i=lgn;i>=0;i--)
{
if(dep[f[u][i]]>=dep[v]) u=f[u][i];
if(u==v) return u;//如果相等直接返回（因为此时u的深度是小于等于v的深度的，所以不用考虑这个点是否为最近的公共祖先）
}//使u点与v点深度相同（利用了2进制的原理）
for(register int i=lgn;i>=0;i--)
{
if(f[u][i]!=f[v][i])
{
u=f[u][i]; v=f[v][i];
}
}//在u，v不重合的情况下尽量将它们向上跳（因为重合后有可能不是它们最近的公共祖先）
return f[u][0];//此时将u（或v）向上跳一格即是答案
}
```
by mcyqwq @ 2019-02-16 22:39:22
@[Dark_Van](/space/show?uid=112720) 可以参考一下蒟蒻我的代码，其中lgn=log2(n)
by mcyqwq @ 2019-02-16 22:40:40
@[__CZK__](/space/show?uid=121908)
窝按您的代码写了一下，结果RE了（输入"3 2"）之后就RE了QAQ
by Dark_Van @ 2019-02-17 10:08:07
```cpp
int solve(int a,int b){
if(d[a]<d[b])swap(a,b);
int lgn=log2(d[a])+1;
for(int i=lgn;i>=0;i--){
if(d[upto[a][i]]>=d[b])a=upto[a][i];
if(a==b)return a;
}
for(int i=lgn;i>=0;i++){
if(upto[a][i]!=upto[b][i]){
a=upto[a][i];b=upto[b][i];
}
}
return upto[a][0];
}
```
by Dark_Van @ 2019-02-17 10:08:58
@[__CZK__](/space/show?uid=121908)
现在又是WA和TLE了。。。
30分心塞qwq
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 500001;
inline int read(){
int x=0,w=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')w=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*w;
}
int n,t,root;
int upto[MAXN][25],d[MAXN]={0},first[MAXN],lg[MAXN];
struct edge{
int u,v,next;
}e[2*MAXN];
int tot=0;
void insert(int u,int v){
++tot;e[tot].u=u;e[tot].v=v;e[tot].next=first[u];first[u]=tot;
}
void init(int u,int fa){
d[u]=d[fa]+1;
upto[u][0]=fa;
for(int k=1;(1<<k)<=d[u];k++){
upto[u][k]=upto[upto[u][k-1]][k-1];
}
for(int i=first[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(v!=fa)init(v,u);
}
}
int solve(int a,int b){
if(d[a]<d[b])swap(a,b);
while(d[a]>d[b]){
a=upto[a][lg[d[a]-d[b]]-1];
}
if(a==b)return a;
for(int k=lg[d[a]]-1;k>=0;k--)
if(upto[a][k]!=upto[b][k]){
a=upto[a][k];b=upto[b][k];
}
return upto[a][0];
}
int main(){
memset(first,-1,sizeof(first));
n=read();t=read();root=read();
for(int i=1;i<n;i++){
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
init(root,0);
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(i<<lg[i-1]==i);//预处理lg[i]=log2(i)+1
for(int i=1;i<=t;i++){
int a=read(),b=read();
printf("%d\n",solve(a,b));
}
return 0;
}
```
by Dark_Van @ 2019-02-17 11:37:30
dalao帮我看看嘛qwq
by Dark_Van @ 2019-02-17 11:38:09
@[__CZK__](/space/show?uid=121908)
当我没说，预处理``lg[i]=log2(i)+1``的时候写错了orz
by Dark_Van @ 2019-02-17 11:50:02