打卡第三天 树形DP提升 基环树

P2607 [ZJOI2008] 骑士

题意：

有n个骑士，每个人都有自己最讨厌的骑士i（不是自己）和战力c，请从这群骑士中选择一群骑士，使这里的每个骑士都不会遇到最讨厌的骑士且战力总和最大。（别人都打过来了还挑三拣四）

思路：

初一看，哇！没有上司的舞会，送分题啊！再一看，似乎有点不对，好像没有根root？

这题有n个点n条边，也就是说，这是一个有向有环图(*+﹏+*)~，那么，如何处理那个环就是最大的问题了

比如样例

这种情况下肯定不能直接树形DP（不存在根），考虑删去一条边。

现在能进行树形DP了，记f[x][0]为现在处理x时不选，f[x][1]为现在处理x时选。

定义若x讨厌y，则x为y的父节点jie

void dp (int x) {//vd[x] -> whether we deal with x or not  f[x][0/1] -> dp memory
    vd[x] = 1;

    f[x][0] = 0;
    f[x][1] = att[x];

    for (int i = 0; i < fa[x].size(); i++) {
        int y = fa[x][i];

        if (!vd[y]) dp(y);

        f[x][0] += max(f[y][0],f[y][1]);
        f[x][1] += f[y][0];
    }
}

 接下来的问题就是找环了，因为每个人只有一个讨厌的人，所以可以按这条路看成一个链表，记v[x]表示搜过了，如果发现在处理v[x]之前v[x] = true,表明已经发现了环的一个点。

void dfs (int x) {
    if (v[x]) {
        return;
    }

    v[x] = true;

    dfs(son[x]);
}

接下来就是dp,dfs和f数组之间的联系了，找到v[x]后，root = x，此时删除root - son[root]的这条边，唯一限制条件就是root与son[root]二者最多只能选其一(可以都不选)，则答案为max(f[root][0],f[son[root]][0]) 。因为对于root = x,root = son[x]根不同，所对应的树结构类似但权限不同，所以需要处理dp(x)和dp(son[x])

void dp (int x) {
    vd[x] = 1;
    v[x] = 1;

    f[x][0] = 0;
    f[x][1] = att[x];

    for (int i = 0; i < fa[x].size(); i++) {
        int y = fa[x][i];

        if (y == root) {
            side = x;
            continue;
        }

        if (!vd[y]) dp(y);

        f[x][0] += max(f[y][0],f[y][1]);
        f[x][1] += f[y][0];
    }
}

void dfs (int x) {
    if (v[x]) {
        root = x;

        long long t = 0;

        dp(x);
        t = max(f[root][0],f[side][0]);

        root = side;
        memset(f,0,sizeof(f));
        memset(vd,0,sizeof(vd));
        dp(root);

        res += max(t,max(f[root][0],f[side][0]));
        return;
    }

    v[x] = true;

    dfs(son[x]);
}

最后在主函数里while循环1~n找环，完结撒花

//AC代码



#include 
#include 
#define maxn 1000005

using namespace std;

int n;
vector fa[maxn];
int son[maxn];
int att[maxn];
bool v[maxn] = {false};
long long res = 0;

long long f[maxn][2];
int root;
int side;
bool vd[maxn] = {false};

void dp (int x) {
    vd[x] = 1;
    v[x] = 1;

    f[x][0] = 0;
    f[x][1] = att[x];

    for (int i = 0; i < fa[x].size(); i++) {
        int y = fa[x][i];

        if (y == root) {
            side = x;
            continue;
        }

        if (!vd[y]) dp(y);

        f[x][0] += max(f[y][0],f[y][1]);
        f[x][1] += f[y][0];
    }
}

void dfs (int x) {
    if (v[x]) {
        root = x;

        long long t = 0;

        dp(x);
        t = max(f[root][0],f[side][0]);

        root = side;
        memset(f,0,sizeof(f));
        memset(vd,0,sizeof(vd));
        dp(root);

        res += max(t,max(f[root][0],f[side][0]));
        return;
    }

    v[x] = true;

    dfs(son[x]);
}

int main () {

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> att[i] >> son[i];
        fa[son[i]].push_back(i);
    }

    int i = 1;
    while (i <= n) {
        if (!v[i]) {
            dfs(i);
        }
        i++;
    }

    cout << res << endl;

    return 0;
}