部分已改,求调
```c++
#include<iostream>
#include<vector>
#define a_ de[a]
#define b_ de[b]
using namespace std;
vector<int> v[500050];
int n,m,s;
int x,y,ans;
int de[500050],fa[500050][20];
int lg[500050];
void dfs(int d,int f)
{
fa[d][0]=f,de[d]=de[f]+1;
int i=1;
while(fa[d][i-1]){fa[d][i]=fa[fa[d][i-1]][i-1];i++;}
for(auto xx : v[d]) if(xx-f) dfs(xx,d);
}
int Lcm(int a,int b)
{
int l;
if(a_<b_){int t=a;a=b,b=t;}
l=lg[a_-b_];
while(a_-b_){if(de[fa[a][l]]<=b_) a=fa[a][l];l--;}//推测是该行代码导致RE
if(a==b) return a;
l=lg[a_];
while(fa[a][0]-fa[b][0]){if(fa[b][l]-fa[a][l]) b=fa[b][l],a=fa[a][l];l--;}
return fa[a][0];
}
int main()
{
//freopen("P3379_1.in","r",stdin);
//freopen("P3379.out","w",stdout);
cin>>n>>m>>s;
for(int i=1;i<n;i++)
{
lg[i+1]=lg[(i+1)/2]+1;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(s,0);
for(int i=1;i<=m;i++)
{
cin>>x>>y;
ans=Lcm(x,y);
cout<<ans<<'\n';
}
return 0;
}
```
by protractor @ 2024-02-17 22:02:28
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,s,head[500010],cnt=0,dep[500010],p[500010][25];
bool vis[500010];
struct node {
int to,nxt;
} e[1000010];
void add(int x,int y) {
e[++cnt].nxt=head[x];
e[cnt].to=y;
head[x]=cnt;
}
void dfs(int u) {
vis[u]=1;
for(int i=head[u]; i!=-1; i=e[i].nxt) {
int v=e[i].to;
if(!vis[v]) {
dep[v]=dep[u]+1;
p[v][0]=u;
dfs(v);
}
}
}
void init() {
for(int j=1; (1<<j)<=n; j++)
for(int i=1; i<=n; i++)
p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
for(int i=20; i>=0; i--)
if(dep[p[u][i]]>=dep[v]) u=p[u][i];
if(u==v) return u;
for(int i=20; i>=0; i--) {
if(p[u][i]!=p[v][i]) {
u=p[u][i];
v=p[v][i];
}
}
return p[u][0];
}
int main() {
cin>>n>>m>>s;
memset(head,-1,sizeof(head));
for(int i=1,x,y; i<n; i++) {
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(s);
init();
for(int k=1,x,y; k<=m; k++) {
cin>>x>>y;
if(y==s||x==s) cout<<s<<endl;
else cout<<lca(x,y)<<endl;
}
return 0;
}
```
by The_43_Bachelor @ 2024-02-28 16:31:22