bzoj1040: [ZJOI2008]骑士

树形DP，加上环状DP

环状DP就把它当成一条链来做，特殊处理头与最后的关系

const int N = 1000010;
LL Dp[N][2];
int n, Dat[N], C[N], Cnt[N] = {0};

inline void Input() {
	scanf("%d", &n);
	For(i, 1, n) {
		scanf("%d%d", &Dat[i], &C[i]);
		Dp[i][0] = 0, Dp[i][1] = Dat[i], Cnt[C[i]]++;
	}
}

inline void Updata(LL *A, LL *B) {
	A[0] += max(B[0], B[1]), A[1] += B[0];
}

LL Cdp[2][2];
inline void Circle(LL *Las) {
	Rep(i, 2)
		Rep(j, 2) Cdp[i][j] = 0;
	Cdp[0][0] = Las[0], Cdp[1][1] = Las[1];
}
inline void UpCir(LL *A) {
	LL T[2][2];
	Rep(i, 2)
		T[i][0] = max(Cdp[i][0], Cdp[i][1]) + A[0], T[i][1] = Cdp[i][0] + A[1];
	Rep(i, 2)
		Rep(j, 2) Cdp[i][j] = T[i][j];
}

inline void Solve() {
	static queue<int> Q;
	For(i, 1, n)
		if(!Cnt[i]) Q.push(i);
	for(; sz(Q); Q.pop()) {
		int Now = Q.front();
		Updata(Dp[C[Now]], Dp[Now]);
		if(!(--Cnt[C[Now]])) Q.push(C[Now]);
	}
	
	LL Ans = 0;
	For(i, 1, n)
		if(Cnt[i]) {
			Cnt[i] = 0;
			Circle(Dp[i]);
			for(int T = C[i]; T != i; T = C[T]) UpCir(Dp[T]), Cnt[T] = 0;
			Ans += max(Cdp[1][0], max(Cdp[0][0], Cdp[0][1]));
		}
	cout << Ans << endl;
}

int main() {
	Input();
	Solve();
	return 0;
}