「Bzoj 1040」「ZJOI2008」骑士 (基环树DP)

bzoj 1040
环套树DP相关解法
本题$n$个点$n$条边，显然是基环树DP。
然而没有保证整幅图都是连通的，所以这要处理一个基环树森林，每棵树树形DP后的答案累加即可，dp方程类似于没有丧尸上司的舞会

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000000 + 5;
struct edge {
    int v;
}ed[MAXN * 2];
int n, en, wi[MAXN], Pu, Pv, PE, vi[MAXN];
LL dp[MAXN][2];
vector<int> G[MAXN];
void ins(int a, int b) {
    en++, ed[en].v = b, G[a].push_back(en);
}
void tdp(int u, int fa) {
    dp[u][0] = 0, dp[u][1] = wi[u]; 
    for (int i=0;i<G[u].size();i++) {
        if (G[u][i] == PE || G[u][i] == (PE ^ 1)) continue;//已经断开，不能通过，否则有后效性 
        edge p = ed[G[u][i]];
        int v = p.v;
        if (v != fa) {
            tdp(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
}
void dfs(int u, int fa)  {
    for (int i=0;i<G[u].size();i++) {
        edge p = ed[G[u][i]];
        int v = p.v;
        if (v != fa) {
            if (!vi[v]) vi[v] = true, dfs(v, u); 
                else Pu = u, Pv = v, PE = G[u][i];//找断开不构成环的边 
        }
    }
}
void clean() {
    en = -1;//边从0开始，方便找出该边的反边 
    for (int i=0;i<=n;i++) vi[i] = false, G[i].clear();
}
void solve() {
    clean(); 
    for (int i=1;i<=n;i++) {
        int x;
        scanf("%d%d", &wi[i], &x);
        ins(x, i), ins(i, x);//看似有向实质无向 
    }
    LL ans = 0;
    for (int i=1;i<=n;i++) {//基环树森林一一处理 
        if (!vi[i]) {
            dfs(i, -1);
            tdp(Pu, -1);
            LL tmp = dp[Pu][0];
            tdp(Pv, -1);
            tmp = max(tmp, dp[Pv][0]);
            ans += tmp;
        }
    }
    printf("%lld\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d", &n), solve();
    return 0;
}