记录编号	593827	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.792 s
提交时间	2024-09-17 12:13:57	内存使用	9.51 MiB

#include<bits/stdc++.h>
#define N 1000010 
using namespace std;
typedef long long ll;
int fa[N];
ll g[N],f[N],val[N];
int to[N<<1],nxt[N<<1],head[N],tot;
int cnt,ra[N],rb[N];
inline void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
int find(int x)
{
	return fa[x]==x?x:(fa[x]=find(fa[x]));
}
void dfs(int pos,int fa)
{
	f[pos]=val[pos];
	g[pos]=0;
	for(int i=head[pos];i;i=nxt[i])
	{
		if(to[i]==fa) continue;
		dfs(to[i],pos);
		f[pos]+=g[to[i]];
		g[pos]+=max(f[to[i]],g[to[i]]);
	}
}
int main()
{
	freopen("bzoj_1040.in","r",stdin);
	freopen("bzoj_1040.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
	}
	ll ans=0;
	for(int b,i=1;i<=n;i++)
	{
		scanf("%lld%d",&val[i],&b);
		if(find(i)!=find(b))
		{
			add(b,i);add(i,b);
			fa[find(b)]=find(i);
		}
		else
		{
			ra[++cnt]=i;
			rb[cnt]=b;
		}
	}
	ll maxn=0;
	for(int i=1;i<=cnt;i++)
	{
		dfs(ra[i],0),maxn=g[ra[i]];
		dfs(rb[i],0),maxn=max(maxn,g[rb[i]]);
		ans+=maxn;
	}
	cout<<ans;
	return 0;
}