~~打个树剖可以解决上述所有问题~~
by NaCly_Fish @ 2019-02-09 17:43:49
@[NaCly_Fish](/space/show?uid=115864) 树剖70分 数据点#2#9 MLE #10 WA 求查错
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
const int N=5e5+5;
int n,q,s;
int nxt[N],fir[N],to[N],siz[N],son[N],fa[N],dep[N],top[N],tot;
inline int read()
{
char c=getchar();
int sign=1,x=0;
while(c<'0'||c>'9')
{
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*sign;
}
inline void addedge(int x,int y)
{
nxt[++tot]=fir[x];
fir[x]=tot;
to[tot]=y;
return;
}
inline void dfs1(int now,int lst)
{
int e,v;
siz[now]=1; fa[now]=lst; dep[now]=dep[lst]+1;
for(e=fir[now];v=to[e],e;e=nxt[e])
{
if(v!=lst)
{
dfs1(v,now);
siz[now]+=siz[v];
if(siz[v]>siz[son[now]]) son[now]=v;
}
}
return;
}
inline void dfs2(int now,int lst)
{
int e,v;
if(son[now])
{
top[son[now]]=top[now];
dfs2(son[now],now);
}
for(e=fir[now];v=to[e],e;e=nxt[e])
{
if(!top[v])
{
top[v]=v;
dfs2(v,now);
}
}
return;
}
inline int LCA(int u,int v)
{
int x=top[u],y=top[v];
while(x!=y)
{
if(dep[x]<dep[y])
{
swap(u,v);
swap(x,y);
}
u=fa[x]; x=top[u];
}
if(dep[u]>dep[v]) return v;
else return u;
}
int main()
{
int u,v;
n=read(); q=read(); s=read();
for(register int i=1;i<n;i++)
{
u=read(); v=read();
addedge(u,v); addedge(v,u);
}
dfs1(s,0);
top[s]=s;
dfs2(s,0);
for(register int i=1;i<=q;i++)
{
u=read(); v=read();
printf("%d\n",LCA(u,v));
}
return 0;
}
```
by mcyqwq @ 2019-02-09 18:00:38
@[__CZK__](/space/show?uid=121908) 是不是lgn小了
by 一叶知秋。 @ 2019-02-09 18:03:09
@[__CZK__](/space/show?uid=121908) 而且u，v不是要跳到一起吗
by 一叶知秋。 @ 2019-02-09 18:06:04
@[__CZK__](/space/show?uid=121908) ```cmath```里的```log```是$\lg$，也就是以$10$为底的，所以```lgn=log(n)+1```太小了
by GKxx @ 2019-02-09 18:08:38
@[__CZK__](/space/show?uid=121908) 打错了，lgN开小了
by 一叶知秋。 @ 2019-02-09 18:10:37
@[吴蕴章](/space/show?uid=71403) @[GKxx](/space/show?uid=72071) 改了之后不开O2 TLE
开了O2MLE
by mcyqwq @ 2019-02-09 18:13:06
@[吴蕴章](/space/show?uid=71403) @[GKxx](/space/show?uid=72071) 谢谢两位大佬 A掉了
原来是存边的数组开小了
by mcyqwq @ 2019-02-09 18:30:04