[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;
} |