求助QWQ
查看原帖
求助QWQ
554480
行者学数学楼主2021/9/16 20:42

请问哪里有bug,第二个点过不去,谢谢各位大佬

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
vector<pair<int,int> > link[1001];
int dis[1001]={0},level[1001]={0},parent[1001]={0};
int fa[23][1001]={0};
void compute(int pare,int root)
{
    for(int i=0;i<link[root].size();i++)
    {
        int child=link[root][i].first,w=link[root][i].second;
        if(child==pare)  continue;
        dis[child]=dis[root]+w;
        fa[0][child]=root;
        level[child]=level[root]+1;
        compute(root,child);
    }
}
int lca(int u,int v)
{
    if(level[u]<level[v])   swap(u,v);
    for(int i=22;i>=0;i--)
    {
        if(fa[i][u]==-1||fa[i][u]==0)   continue;
        if(level[fa[i][u]]>=level[v])  u=fa[i][u];
        if(u==v)   return v;
    }
    for(int i=22;i>=0;i--)
    {
        if(fa[i][u]!=fa[i][v])
        {
            u=fa[i][u];
            v=fa[i][v];
        }
    }
    return fa[0][u];
}
int main()
{
    int N,Q;
    cin>>N>>Q;
    fa[0][1]=-1;
    for(int i=0;i<N-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        link[u].push_back({v,w});
        link[v].push_back({u,w});
    }
    parent[1]=-1;
    dis[1]=0;
    level[1]=1;
    compute(-1,1);
    for(int k=1;k<23;k++)
    {
        queue<int> q;
        q.push(1);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            if(u==1)  fa[k][u]=-1;
            else fa[k][u]=fa[k-1][fa[k-1][u]];
            for(int i=0;i<link[u].size();i++)
            {
                int v=link[u][i].first;
                if(v==parent[u])  continue;
                parent[v]=u;
                q.push(v);
            }
        }
    }
    vector<int> res(Q);
    for(int i=0;i<Q;i++)
    {
        int u,v;
        cin>>u>>v;
        res[i]=dis[u]+dis[v]-2*dis[lca(u,v)];
    }
    for(int i=0;i<Q;i++)  cout<<res[i]<<endl;
}
2021/9/16 20:42
加载中...