[ZJOI2008] 骑士

archer233 / 2024-10-10 / 原文

$基环树DP$
https://www.luogu.com.cn/problem/P2607
$将基环树上面的环破开成树就能进行如同《没有上司的舞会》的树形DP$
$没有上司的舞会:$https://www.luogu.com.cn/problem/P1352
$具体实现困难之处在于如何破环成树，其实只需要主要到对于树上的一个环，将环上的两个节点记录就能算出树的不同选取方式的最大值$
$在下方代码中的find用于找到两个不同的根节点对其进行dfs 因为是单向边所以只需要保证环不会回到自己即可$
code：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back()
const int N = 1e5 + 10;

void solve() {
    int n;cin>>n;
    vector dp(n+1,vector<int>(2));
    vector G(n+1,vector<int>());
    int r1,r2;
    vector<int>vis(n+1),w(n+1);
    for(int i=1,x;i<=n;i++){
        cin>>w[i]>>x;
        G[x].push_back(i);
    }
    function<void(int,int)>find=[&](int x,int root){
        vis[x]=1;
        for(auto &son:G[x]){
            if(son==root){
                r1=x;
                r2=son;return;
            }
            if(vis[son])continue;
            find(son,root);
        }
    };
    function<int(int,int)>dfs=[&](int x,int root){
        dp[x][0]=0,dp[x][1]=w[x];
        for(auto &son:G[x]){
            if(son==root)continue;
            dfs(son,root);
            dp[x][0]+=max(dp[son][1],dp[son][0]);
            dp[x][1]+=dp[son][0];
        }
        return dp[x][0];
    };
    int sum=0;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        r1=r2=0;
        find(i,i);
        if(r1){
            int res1=dfs(r1,r1);
            int res2=dfs(r2,r2);
            sum+=max(res1,res2);
        }
    }
    cout<<sum;
}

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

    solve();
}