求助,倍增法全WA
查看原帖
求助,倍增法全WA
540148
Universal_xtr楼主2021/11/13 20:22

如题,想了很久还是找不到错,求各位大佬相助,感谢!

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll n,m,s;
vector<ll> v[600001];
ll f[600001][22];
ll depth[600001];
void dfs(ll x,ll fa){
    f[x][0]=fa;depth[x]=depth[fa]+1;
    for(ll i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(ll i=0;i<v[x].size();i++){
        ll tmp=v[x][i];
        if(tmp==fa)continue;
        dfs(tmp,x);
    }
}
ll LCA(ll x,ll y){
    if(depth[x]>depth[y])swap(x,y);
    for(ll i=20;i>=0;i--)if(depth[f[x][i]]>=depth[y])x=f[x][i];
    if(x==y)return x;
    for(ll i=20;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
    return f[x][0];
}
int main(){
    cin>>n>>m>>s;
    for(ll i=1;i<n;i++){ll a,b;cin>>a>>b;v[a].push_back(b);v[b].push_back(a);}
    dfs(s,0);
    while(m--){
        ll x,y;cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}
2021/11/13 20:22
加载中...