每日一题6.13(基环树dp)

495684945

https://www.luogu.com.cn/problem/P2607

Fengyj

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n;
    cin>>n;

    vector<int>fa(n+1);
    iota(fa.begin(),fa.end(),0);
    vector<int>a(n+1);
    vector<vector<int>>adj(n+1);

    auto find=[&](auto &&find,int x){
        if(x==fa[x]) return x;
        return fa[x]=find(find,fa[x]);
    };

    auto merge=[&](int x,int y){
        fa[find(find,x)]=find(find,y);
    };

    vector<array<int,2>>p;
     
    
    for(int i=1;i<=n;i++){
        int x;
        cin>>a[i]>>x;

        if(find(find,i)==find(find,x)){
            p.push_back({i,x});
            continue;
        }
        
        merge(x,i);
        adj[x].push_back(i);
        adj[i].push_back(x);

    }
    
    vector<array<int,2>>dp(n+1);
    int ans=0;

    auto dfs=[&](auto dfs,int u,int pa )->void{
        dp[u][0]=0;
        dp[u][1]=a[u];

        for(auto v:adj[u]){
            if(v==pa) continue;
            dfs(dfs,v,u);

            dp[u][1]+=dp[v][0];
            dp[u][0]+=max(dp[v][0],dp[v][1]);
        }
      
    };

    for(auto r:p){
        int r1=r[0],r2=r[1];
        int res=0;
        dfs(dfs,r1,0);
        int res1=dp[r1][0];
        dfs(dfs,r2,0);
        int res2=dp[r2][0];
        ans+=max(res1,res2);
    }
    cout<<ans<<'\n';
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t=1;
    //cin>>t;

    while(t--){
        solve();
    }


    return 0;
}