记录编号	460967	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	kemoto	是否通过	通过
代码语言	C++	运行时间	1.307 s
提交时间	2017-10-18 20:36:00	内存使用	79.47 MiB

// By Cooook.
#include <bits/stdc++.h>
#define MAXN 1000005
#define int long long 
int n,l,r,first[MAXN],e = 2,val[MAXN],Ans,f[MAXN][2];
bool vis[MAXN],used[MAXN<<1],have;
 
 
template <typename _t>
inline _t read() {
    _t x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return x * f;
}
 
struct node{
    int u,v,next;
}a[MAXN<<1];
 
inline void push(int u,int v) {
    a[e].u = u; a[e].v = v;
    a[e].next = first[u]; first[u] = e++;
}
 
inline void Get(int u,int fa) {
    if (have) return;
    vis[u] = true;
    for (int i = first[u]; i; i = a[i].next) {
        register int v = a[i].v;
        if (v == fa) continue;
        if (vis[v]) {
            l = u, r = v; 
            used[i] = used[i^1] = true;
            have = true;
            break;
        }
        Get(v,u);
        if (have) return;
    }
}
 
inline void dp(int u,int fa,int flag) {
    vis[u] = true;
    if (u == flag) f[u][1] = 0;
    else f[u][1] = val[u];
    f[u][0] = 0;
    for (int i = first[u]; i; i = a[i].next) {
        register int v = a[i].v;
        if (v == fa || used[i]) continue;
        dp(v,u,flag);
        f[u][1] += f[v][0];
        f[u][0] += std::max(f[v][1],f[v][0]);
    }
}
 
signed main() {
    freopen("bzoj_1040.in","r",stdin);
    freopen("bzoj_1040.out","w",stdout);
    n = read<int>();
    for (int i = 1; i <= n; i++) {
        val[i] = read<int>();
        register int v = read<int>();
        push(v,i); push(i,v);
    }
    for (int i = 1,tmp; i <= n; i++) if (!vis[i]) {
        have = false;
        Get(i,0);
        dp(l,0,r);
        tmp = 0;
        tmp = std::max(tmp,std::max(f[l][0],f[l][1]));
        dp(r,0,l);
        tmp = std::max(tmp,std::max(f[r][0],f[r][1]));
        Ans += tmp;
    }
    return printf("%lld\n",Ans),getchar(),getchar(), 0;
}