记录编号	576691	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	2.313 s
提交时间	2022-10-15 09:22:21	内存使用	74.40 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1000010;
int n, a[MAXN], b[MAXN], vis[MAXN], fa[MAXN], ans, f[2][MAXN], rt;
vector<int> cd[MAXN];
void dfs2(int x) {
	vis[x] = 1;
	f[1][x] = a[x];
	f[0][x] = 0;
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		if(u == rt) {
			f[1][u] = -1e9;
			continue;
		}
		dfs2(u);
		f[0][x] += max(f[0][u], f[1][u]);
		f[1][x] += f[0][u];
	}
}
void dfs(int x) {
	vis[x] = 1;
	rt = x;
	while(!vis[fa[rt]]) {
		rt = fa[rt];
		vis[rt] = 1;
	}
//	cout << rt << "     " << fa[rt] << "     ";
	dfs2(rt);
	vis[rt] = 1;
	int w = max(f[1][rt], f[0][rt]);
	rt = fa[rt];
	dfs2(rt);
//	cout << rt << endl;
	ans += max(w, max(f[1][rt], f[0][rt]));
}
signed main() {
    freopen("bzoj_1040.in", "r", stdin);
    freopen("bzoj_1040.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i] >> b[i];
		cd[b[i]].push_back(i);
//		cd[i].push_back(b[i]);
		fa[i] = b[i];
	}
	for(int i = 1; i <= n; i ++) {
		if(!vis[i]) {
			dfs(i);
//			cout << f[1][i] << ' ' << f[0][i] << endl;
		}
	}
	cout << ans; 
	return 0;
}