到底错哪了呜呜┭┮﹏┭┮
查看原帖
到底错哪了呜呜┭┮﹏┭┮
914594
leoluuu楼主2024/3/5 20:29

0分,只过了Subtask 0的第一个测试点,跪求大佬帮忙找到错误orz

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
#define int long long 
vector<int> g[N];
int fa[N][18],depth[N];
int arr[N],cost1[N],cost2[N];
int diff[N],org[N];
queue<int> q;
int vis[N];
void bfs(int root){
    memset(depth,0x3f,sizeof depth);
    depth[0]=0;
    depth[root]=1;
    q.push(root);
    while(q.size()){
        
        int tmp = q.front();
        q.pop();
        for(auto x:g[tmp]){
            if(depth[x]>depth[tmp]+1){
                // cout<<"________________"<<endl;
                q.push(x);// 别忘入队
                depth[x] = depth[tmp]+1;
                fa[x][0]=tmp;
                for(int i=1;i<=17;++i){
                    fa[x][i]=fa[fa[x][i-1]][i-1];
                }
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    
    for(int i=17;i>=0;--i){
        if(depth[fa[a][i]]>=depth[b]) a = fa[a][i];//注意等号
    }

    if(a==b) return a;
    for(int i=17;i>=0;--i){
        if(fa[a][i]!=fa[b][i]){
            a = fa[a][i];
            b =fa[b][i];
        }
    }
    return fa[a][0];
}
void dfs(int u){
    org[u]=diff[u];
    for(auto x:g[u]){
        if(x==fa[u][0]) continue;
        dfs(x);//递归别忘dfs
        org[u]+=diff[x];
    }
    return ;
}
signed main(){
    // cout<<log2(N)<<endl;17.6097   0-17
    int n,a,b,c1,c2,root;
    scanf("%lld",&n);
    // vis[1]=1;// 这里有问题
    for(int i=1;i<n;++i){
        scanf("%lld%lld%lld%lld",&a,&b,&c1,&c2);
        g[a].push_back(b);
        g[b].push_back(a);
        if(i==1){
            root=b;
            vis[b]=1;
        }
        if(vis[a]) swap(a,b);
        cost1[a] = c1;
        cost2[a] = c2;
        vis[a]=1;
        // 这里不太对,对
        // if(a>b) swap(a,b);
        // cost1[b] = c1;
        // cost2[b] = c2;
    }
    bfs(root);
    for(int i=2;i<=n;++i){
        // cout<<i<<"     lca"<<lca(1,i)<<endl;
        //边权差分
        diff[i-1]++;// 注意审题
        diff[i]++;
        diff[lca(i-1,i)]-=2;

    }
    dfs(root);
    int ans = 0;

    for(int i=1;i<=n;++i){
        if(i==root) continue;
        if(cost1[i]*org[i]<cost2[i]) ans +=cost1[i]*org[i];
        else ans += cost2[i];
    }
    cout<<ans<<endl;
    return 0;
}
2024/3/5 20:29
加载中...