思路

图可能会有多个连通块，整个图最多有一个环。 基环树的题目，对每一块找环切断，然后树形dp。 环的切断方式有两种，从那条边的起始点出发做两次dp， 当前块的答案就加上两次dp结果的较大值。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int maxn=1e6+7;

//int read(){	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}

struct Edge{
	int nxt,to;
}e[maxn];

int n,deg[maxn],vis[maxn],mrky,mrke;
int f[maxn][2],ans,tmp;
int a[maxn],v[maxn];
int head[maxn],cnt=0;

inline void addedge(int u,int v){
	e[++cnt]=(Edge){head[u],v};
	head[u]=cnt;
}

void dp(int x){
	vis[x]=1;
	f[x][1]=a[x];f[x][0]=0;
	for(int i=head[x];i;i=e[i].nxt){
		int y=e[i].to;
		if(y==mrky){ 
			f[y][1]=-inf;
			continue;
		}
		dp(y);
		f[x][0]+=max(f[y][0],f[y][1]);
		f[x][1]+=f[y][0];
	}
}

void find_loop(int x){
	vis[x]=1;
	if(vis[v[x]]) mrky=x; //讨厌的人已经被选了 
	else find_loop(v[x]);
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>v[i];
		addedge(v[i],i);
	}
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		find_loop(i);
		dp(mrky);
		tmp=max(f[mrky][0],f[mrky][1]);
		mrky=v[mrky];
		dp(mrky);
		ans+=max(tmp,max(f[mrky][0],f[mrky][1]));
	}
	cout<<ans<<"\n";
	return 0;
}