2026-08-08 14:27:56
发布于:上海
求调教 70分代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,fa[N][(int)log2(N)],dep[N],x,y;
vector<int>edge[N];
void dfs(int u,int pre){
dep[u]=dep[pre]+1;
fa[u][0]=pre;
for(int i=1;i<=(int)log2(n);i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int v:edge[u]){
if(v==pre)continue;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=(int)log2(n);i>=0;i--){
if(dep[u]-(1<<i)>=dep[v]){
u=fa[u][i];
}
}
if(u==v)return u;
for(int i=(int)log2(n);i>=0;i--){
if(fa[u][i]==fa[v][i])continue;
u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(s,0);
for(int i=1;i<=m;i++){
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}
全部评论 3
格式有点问题,中间少了几个==号
5天前 来自 浙江
0以下为修正后代码(倍增法求LCA)
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,s,fa[N][(int)log2(N)+1],dep[N],x,y;
vector<int>edge[N];
void dfs(int u,int pre){
dep[u]=dep[pre]+1;
fa[u][0]=pre;
for(int i=1;i<=(int)log2(n);i++){
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int v:edge[u]){
if(vpre)continue;
dfs(v,u);
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=(int)log2(n);i>=0;i--){
if(dep[u]-(1<<i)>=dep[v]){
u=fa[u][i];
}
}
if(uv)return u;
for(int i=(int)log2(n);i>=0;i--){
if(fa[u][i]==fa[v][i])continue;
u=fa[u][i],v=fa[v][i];
}
return fa[u][0];
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(s,0);
for(int i=1;i<=m;i++){
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}5天前 来自 浙江
0你的fa数组第二维应该开(int)log2(N)+1,应为如果你要倍增到2log2(N)的位置那其实需要log2(N)+1的空间,因为20也要没有算入,如果加上2^0的位置空间就应该多开1
5天前 来自 浙江
0谢谢,知道了,我当时调出来了
4天前 来自 上海
0行
4天前 来自 浙江
0





















有帮助,赞一个