bzoj 1040 基向内环树dp

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int, int>
#define y1 skldjfskldjg
#define y2 skldfjsklejg

using namespace std;

const int N = 1e6 + 7;
const int M = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 +7;

int n, tot, a[N], fa[N], b[N], head[N];
bool vis[N];
LL f[N][2];

struct Edge {
    int to, nx;
} edge[N << 1];

void add(int u, int v) {
    edge[tot].to = v;
    edge[tot].nx = head[u];
    head[u] = tot++;
}

int getRoot(int x) {
    return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
}

void dp(int u, int fa, int ban) {
    f[u][0] = 0, f[u][1] = a[u];
    LL tmp[2] = {0};

    for(int i = head[u]; ~i; i = edge[i].nx) {
        int v = edge[i].to;
        if(v == fa || i == ban || (i ^ 1) == ban) continue;
        dp(v, u, ban);

        tmp[0] = f[u][0], tmp[1] = f[u][1];

        tmp[0] = max(tmp[0], f[u][0] + f[v][1]);
        tmp[0] = max(tmp[0], f[u][0] + f[v][0]);
        tmp[1] = max(tmp[1], f[u][1] + f[v][0]);

        f[u][0] = tmp[0], f[u][1] = tmp[1];
    }
}

int main() {
    memset(head, -1, sizeof(head));

    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        add(i, b[i]); add(b[i], i);
        fa[i] = i;
    }

    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        int x = getRoot(i);
        int y = getRoot(b[i]);
        if(x != y) {
            fa[x] = y;
        } else {
            LL ret = 0;
            dp(i, 0, i * 2 - 2);
            ret = max(ret, f[i][0]);
            dp(b[i], 0, i * 2 - 2);
            ret = max(ret, f[b[i]][0]);
            ans += ret;
        }
    }

    printf("%lld
", ans);
    return 0;
}


/*
*/