https://www.luogu.com.cn/discuss/364397

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<list>
#include<map>
using namespace std;
int n;
int f[1000001],v[1000001];
int head[1000001],cnt;
struct edg{
	int next,to;
}edge[2000003];
void add_edge(int u,int v)
{
	edge[++cnt].next=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}
int dp[3][1000001][2],vis[2][1000001];
void DFS(int now,int type)
{
	vis[type][now]=1;
	for(int i=head[now];;i=edge[i].next)
	{
		if(!i) break;
		if(vis[type][edge[i].to]) continue;
		DFS(edge[i].to,type);
		dp[type][now][0]+=max(dp[type][edge[i].to][0],dp[type][edge[i].to][1]);
		dp[type][now][1]+=dp[type][edge[i].to][0];
	}
	dp[type][now][1]+=v[now];
}
int lj,jc=0,jc2,jc3;
int main()
{
	freopen("az.txt","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%d%d",&v[i],&f[i]);
		add_edge(f[i],i);
		add_edge(i,f[i]);
	}
	for(int i=1;i<=n;i++)
		if(!vis[1][i])
		{
			jc2=head[i];
			head[i]=edge[head[i]].next;
			jc3=head[edge[jc2].to];
			head[edge[jc2].to]=edge[head[edge[jc2].to]].next;
			swap(jc,v[i]);
			DFS(i,0);
			swap(jc,v[i]);
			swap(jc,v[edge[jc2].to]);
			DFS(i,1);
			swap(jc,v[edge[jc2].to]);
			lj+=max(max(dp[0][i][0],dp[0][i][1]),max(dp[1][i][0],dp[1][i][1]));
			head[i]=jc2;
			head[edge[jc2].to]=jc3;
		}
	printf("%d",lj);
	return 0;
}

下载不了数据，所以...给个能卡掉的，人看的数据就行了...还请dalao成全juruo