可能。。。是题解的反作弊？？
by TomLovesRita @ 2019-05-17 17:34:44
@[名字好难起啊hh](/space/show?uid=67437) ??
by TomLovesRita @ 2019-05-17 17:34:58
@[名字好难起啊hh](/space/show?uid=67437) [自己](/space/show?uid=106235) @[自己](/space/show?uid=106235) 好评
by yu__xuan @ 2019-05-17 17:36:11
@[SAOKA_](/space/show?uid=25046)
```
lg[i] = lg[i-1] + (1<<lg[i-1] == 1);
```
改为
```
lg[i] = lg[i-1] + (1<<lg[i-1] == i);
```
以及安利下我的模版
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct edge
{
int to,next;
}e[maxn<<1];
int head[maxn],f[maxn][30+5],lg[maxn],dep[maxn];
int size=0;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
void addedge(int u,int v)
{
e[++size].to=v;e[size].next=head[u];head[u]=size;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<=lg[dep[u]];i++)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u];i;i=e[i].next)
{
int to=e[i].to;
if(to==fa)continue;
dfs(to,u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
while(dep[x]>dep[y])
x=f[x][lg[dep[x]-dep[y]]];
if(x==y)
return x;
for(int i=lg[dep[x]];i>=0;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
int n=read(),m=read(),s=read();
for(int i=1;i<=n-1;i++)
{
int u=read(),v=read();
addedge(u,v);
addedge(v,u);
}
for(int i=1;i<=n;i++)
lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
dfs(s,0);
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
printf("%d\n",lca(x,y));
}
return 0;
}
```
by Edward_Elric @ 2019-05-17 17:56:35
为啥要算log
by cosmicAC @ 2019-05-17 18:41:07
@[法兰西万岁](/space/show?uid=58707) 好啊，确实是我写错了
by SAOKA_ @ 2019-05-17 19:35:56
@[法兰西万岁](/space/show?uid=58707) 我感觉…我的模板跟你的…差不多？
by SAOKA_ @ 2019-05-17 19:38:00
@[法兰西万岁](/space/show?uid=58707) 改的那句话是什么意思啊dalao，太菜了刚学OI
by 红色OI再临 @ 2019-06-03 12:17:46
@[红色OI再临](/space/show?uid=57823) 就是处理以2为底的对数(+1)，一个常数优化，因为需要多次调用
by Edward_Elric @ 2019-06-11 19:05:55