#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=0x7f7f7f7f;
const int N=1e4+10;
int n,a,b,tot;
vector<int> g[N];
int dfn[N],f[25][N];
void add(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
void dfs(int u,int fa){
dfn[u]=dfn[fa]+1;
f[0][u]=fa;
for(int i=1;i<=20;i++)
f[i][u]=f[i-1][f[i-1][u]];
for(auto v:g[u])
if(v!=fa) dfs(v,u);
}
int lca(int u,int v){
if(dfn[u]<dfn[v]) swap(u,v);
for(int i=20;i>=0;i--)
if(dfn[f[i][u]]>=dfn[v])
u=f[i][u];
if(u==v) return u;
for(int i=20;i>=0;i--)
if(f[i][u]!=f[i][v])
u=f[i][u],v=f[i][v];
return f[0][u];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>a>>b;
while(!cin.eof()){
int u,v;
char p;
cin>>u;
p=getchar();
while(p==' '){
cin>>v;
add(u,v);
p=getchar();
}
}
dfs(1,0);
for(int i=1;i<=__lg(n);i++)
for(int j=1;j+(1<<i)-1<=n;j++)
f[i][j]=f[i-1][f[i-1][j]];
cout<<lca(a,b);
return 0;
}
发亿下题面
我点进去会403的·
@吴梓峤 请将帖子放到问题讨论区，并将名字改好
（）
看到了，改完了变成0分了
到那个帖子里说吧
已A，此贴结