你使用的暴力求解吗？那肯定会超时啊
by Eason_AC @ 2019-03-30 15:29:24
你可以去看看《信息学奥赛一本通（提高篇）》第246页
by Eason_AC @ 2019-03-30 15:30:13
@[Eason_AC](/space/show?uid=112917) 而且暴力check还是错的
by YZhe @ 2019-03-30 15:31:12
>您可以先看一下我的这个倍增代码：
```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int tmp, n, m, s;
int head[1000006], dep[1000006], f[5000001][30];
struct node {
int v, nxt;
}a[1000006];
void add(int x, int y) {
a[++tmp].v = y;
a[tmp].nxt = head[x];
head[x] = tmp;
}
void dfsFORLca(int x) {
int son;
for(int p = head[x]; p; p = a[p].nxt) {
son = a[p].v;
if(!dep[son]) {
dep[son] = dep[x] + 1;
f[son][0] = x;
int i = 0, po = x;
while(f[po][i]) {
f[son][i + 1] = f[po][i];
po = f[po][i];
i++;
}
dfsFORLca(son);
}
}
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
int lim = sqrt(dep[x]) + 1;
for(int i = lim; i >= 0; --i)
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(x == y) return x;
for(int i = lim; i >= 0; --i)
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int main() {
scanf("%d%d%d", &n, &m, &s);
int x, y;
for(int i = 1; i < n; ++i) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
dep[s] = 1;
dfsFORLca(s);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
}
return 0;
}
```
by Eason_AC @ 2019-03-30 15:35:51
>不好意思格式问题：
```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int tmp, n, m, s;
int head[1000006], dep[1000006], f[5000001][30];
struct node {
int v, nxt;
}a[1000006];
void add(int x, int y) {
a[++tmp].v = y;
a[tmp].nxt = head[x];
head[x] = tmp;
}
void dfsFORLca(int x) {
int son;
for(int p = head[x]; p; p = a[p].nxt) {
son = a[p].v;
if(!dep[son]) {
dep[son] = dep[x] + 1;
f[son][0] = x;
int i = 0, po = x;
while(f[po][i]) {
f[son][i + 1] = f[po][i];
po = f[po][i];
i++;
}
dfsFORLca(son);
}
}
}
int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
int lim = sqrt(dep[x]) + 1;
for(int i = lim; i >= 0; --i)
if(dep[f[x][i]] >= dep[y]) x = f[x][i];
if(x == y) return x;
for(int i = lim; i >= 0; --i)
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
return f[x][0];
}
int main() {
scanf("%d%d%d", &n, &m, &s);
int x, y;
for(int i = 1; i < n; ++i) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
dep[s] = 1;
dfsFORLca(s);
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &x, &y);
printf("%d\n", LCA(x, y));
}
return 0;
}
```
by Eason_AC @ 2019-03-30 15:36:26
@[Eason_AC](/space/show?uid=112917) 谢谢大佬啊
by _谦退_ @ 2019-03-31 17:33:52
@[Tryer](/space/show?uid=117655) 但是我试过的几个样例都是对的啊
by _谦退_ @ 2019-03-31 17:34:22