~~要不要试试这个……~~
```cpp
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
......
```
by wxwoo @ 2019-03-23 15:52:48
别用快速输出，更慢
by skydogli @ 2019-03-23 15:53:11
话说为什么不用`getchar()`而是用`cin.get()`啊
by wxwoo @ 2019-03-23 15:55:21
@[wxwoo](/space/show?uid=116659) 我觉得两者都差不多...
by ⑨baka @ 2019-03-23 15:56:17
~~什么时候更新文文新闻~~
by dreagonm @ 2019-03-23 15:56:32
倍增+O2 ok的啊 最慢的778ms
~~代码丑~~
```cpp
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int n,m,s;
const int maxn=500000+5;
int maxk;
vector<int> G[maxn];
int depth[maxn];
int fa[20][maxn];
inline int read() {
int x=0,w=1;
char ch;
while(ch<'0'||ch>'9') {
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;
}
void dfs(int u,int f,int d) {
depth[u]=d;
fa[0][u]=f;
int len=G[u].size();
for(int i=0; i<len; ++i) {
int v=G[u][i];
if(v!=f) dfs(v,u,d+1);
}
return;
}
void init(int n) {
dfs(s,-1,0);//init了fa[0]和depth
for(int k=0; k<maxk; ++k)
for(int i=1; i<=n; ++i)
if(fa[k][i]<0) fa[k+1][i]=-1;
else fa[k+1][i]=fa[k][fa[k][i]];
return;
}
int lca(int u,int v) {
if(depth[u]>depth[v]) swap(u,v);//u在下边
for(int k=maxk; k>=0; --k)
if((depth[v]-depth[u])>>k&1)
v=fa[k][v];
if(u==v) return u;
for(int k=maxk; k>=0; --k)
if(fa[k][u]!=fa[k][v]) {
u=fa[k][u];
v=fa[k][v];
}
return fa[0][u];
}
int main() {
n=read(),m=read(),s=read();
maxk=floor(log(n+0.0)/log(2.0));
register int x,y;
for(register int i=0; i<n-1; ++i) {
x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
}
init(n);
register int a,b;
for(register int i=0; i<m; ++i) {
a=read(),b=read();
printf("%d\n",lca(a,b));
}
return 0;
}
```
by Acidwits @ 2019-03-23 15:58:36
评测状态
Unaccepted 70
用时: 3732ms / 内存: 55336KB
```cpp
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
const int N=500005;
struct edge
{
int to,next;
}e[N*2];
int head[N],fa[N][20],dep[N],used[N],cnt,lg[N],n;
inline void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y])
x=fa[x][lg[dep[x]-dep[y]]-1];
if(x==y) return x;
for(register int i=lg[n];i>=0;--i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline void dfs(int x,int fah)
{
dep[x]=dep[fah]+1;
for(register int i=1;i<lg[n];++i)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(register int i=head[x];i;i=e[i].next)
if(e[i].to!=fah)
{
fa[e[i].to][0]=x;
dfs(e[i].to,x);
}
}
inline void read(int &x)
{
x=0; char ch=cin.get();
while(!isdigit(ch)) ch=cin.get();
while(isdigit(ch)) x=x*10+ch-'0',ch=cin.get();
}
void print(int x)
{
if(x>9) print(x/10);
putchar(x%10+'0');
}
int main()
{
int m,s;
read(n); read(m); read(s);
for(register int i=1;i<n;++i)
{
int x,y;
read(x); read(y);
add(x,y); add(y,x);
}
for(register int i=1;i<=n;++i)
if((1<<lg[i-1])==i) lg[i]=lg[i-1]+1;
else lg[i]=lg[i-1];
dfs(s,0);
for(register int i=1;i<=m;++i)
{
int x,y;
read(x); read(y);
int sum=lca(x,y);
print(sum);
putchar('\n');
}
return 0;
}
```
by ⑨baka @ 2019-03-23 15:58:38
@[⑨baka](/space/show?uid=90285) ~~为什么我不这么觉得~~
by wxwoo @ 2019-03-23 15:59:03
@[Acid_An](/space/show?uid=88009) 难道是我的倍增有误...
by ⑨baka @ 2019-03-23 15:59:14
@[⑨baka](/space/show?uid=90285) 催更
by 犇犇犇犇 @ 2019-03-23 16:03:06