\(基环树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();
}