记录编号	576976	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 骑士	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.736 s
提交时间	2022-10-19 19:35:31	内存使用	15.29 MiB

#include <bits/stdc++.h>

using i64 = long long;

const int N = 2e6 + 10;
int n, x, y, edge;
i64 f[N][2], a[N];
int e[N], ne[N], h[N], idx;
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

void dfs(int u, int last) {
    st[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if ((i ^ 1) == last) continue;
        if (!st[v]) 
            dfs(v, i);
        else 
            x = u, y = v, edge = i;
    }
}

void dp(int u, int last) {
    f[u][0] = 0, f[u][1] = a[u];
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if ((i ^ 1) == last || i == edge || (i ^ 1) == edge)
            continue;
        dp(v, i);
        f[u][1] += f[v][0];
        f[u][0] += std::max(f[v][1], f[v][0]);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    freopen("bzoj_1040.in", "r", stdin); 
    freopen("bzoj_1040.out", "w", stdout);
    memset(h, -1, sizeof h);
    std::cin >> n;
    for (int i = 1, t; i <= n; ++ i) {
        std::cin >> a[i] >> t;
        add(t, i), add(i, t);
    }
    i64 ans = 0;
    for (int i = 1; i <= n; ++ i) {
        if (!st[i]) {
            dfs(i, -1);
            dp(x, -1);
            i64 t = f[x][0];
            dp(y, -1);
            ans += std::max(t, f[y][0]);
        }
    }
    std::cout << ans << '\n';
    return 0;
}