全部评论 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(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;
    }
    }

    5天前 来自 浙江

    0
  • 你的fa数组第二维应该开(int)log2(N)+1,应为如果你要倍增到2log2(N)的位置那其实需要log2(N)+1的空间,因为20也要没有算入,如果加上2^0的位置空间就应该多开1

    5天前 来自 浙江

    0

热门讨论