P2607 [ZJOI2008] 骑士

难度：紫（省选/NOI−）。

知识点：图论，树形 DP，DFS。

知识点难度（知识点模板题）：绿。

代码长度：中偏短（$52$ 行）

代码难度：较低。

思路

这道题是采用树形 DP 的《没有上司的舞会》的模板的，状态定义为：

$dp[i][0]$ 是以 $i$ 为根的子树不选择这个节点的最大答案。

同理，$dp[i][1]$ 就是选择 $i$ 的最大答案。

但是这道题有一个点要注意，就是如何处理一个环的情况。

我们采取把环给断掉再 DP，那么这个时候我们就在以下的两种情况中选择最大的。

1. 第一种情况：把现在遍历到的节点暂时删掉然后进行 DP。
2. 第二种情况：把现在遍历到的节点的父节点删除然后从父节点开始 DP。

然后，就结束了，就是这么简单。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define int long long
vector <int> e[1000005];
int a[1000005], b[1000005], n, vis[1000005], fa[1000005], dp[1000005][2], ans;
void dfs(int nw, int root) {
    vis[nw] = 1;
    dp[nw][0] = 0;
    dp[nw][1] = a[nw];
    for (int i = 0; i < e[nw].size(); i ++) {
        int to = e[nw][i];
        if (to != root) {
            dfs(to, root);
            dp[nw][0] += max(dp[to][0], dp[to][1]);
            dp[nw][1] += dp[to][0];
        } else dp[to][1] = -1e18;
    }
}
void fc(int nw) {
    vis[nw] = 1;
    int root = fa[nw];
    while (vis[fa[root]] == 0) {
        root = fa[root];
        vis[root] = 1;
    }
    dfs(root, root);
    int tmp = max(dp[root][0], dp[root][1]);
    //删掉这个节点
    vis[root] = 1;
    root = fa[root];
    dfs(root, root);
    ans += max(tmp, max(dp[root][0], dp[root][1]));
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i] >> b[i];
        e[b[i]].push_back(i);
        fa[i] = b[i];
    }
    for (int i= 1; i <= n; i ++) {
        if (vis[i] == 0) {
            fc(i);
        }
    }
    cout << ans;
    return 0;
}