骑士问题

解题思路：

如果将每个骑士向讨厌的人连边，则可以看作每个点只有一条出边，因此这就是一个基环森林。

然后要求我们在基环森林中选出若干个点，使得任意两个点没有公共边，要求选出的最大点权和。

可以发现基环森林中每棵基环树的选法都是独立的，因此我们可以对于每棵基环树单独考虑如何选点。如果是一棵普通的树，我们可以直接用树形 $dp$ 来求，但是本题是一棵基环树，存在循环依赖就没法用 $dp$ 了。

我们可以考虑将一条边断开，取环上某一点 $p$，$p$ 讨厌 $A_p$，则所有方案可以分成两种，一种是选 $p$，一种是不选 $p$，如果我们将 $p \rightarrow A_p$ 这条边断开，那么基环树就会变成一棵树，我们就可以在树上做树形 $dp$ 了，我们要在做树形 $dp$ 的时候把选 $p$ 不选 $p$ 的方案都枚举到，我们可以分别枚举这两种方案。对于不选 $p$ 的情况，此时 $A_p$ 可选可不选，因此 $p \rightarrow A_p$ 这条边就没有意义了，因为此时 $A_p$ 选还是不是和 $p$ 没有关系了，那么这条边删去就不会造成任何影响，我们直接在删完边的树上求一遍树形 $dp$ 即可。

这里的树形 $dp$ 我们设 $f_{u,0}$ 表示在以 $u$ 为根的子树中选若干个点且不选 $u$ 的所有方案的最大值，$f_{u,1}$ 表示在以 $u$ 为根的子树中选若干个点且选 $u$ 的所有方案的最大值。

则状态转移方程也比较好考虑，设 $u$ 的每一个子节点是 $s$，得到以下状态转移方程：

$$ \begin{cases} f_{u,0} = \sum \max{\lbrace f_{s,0}, f_{s,1} \rbrace} \newline f_{u,1} = \sum f_{s,0} \end{cases} $$

最终我们对于 $p$ 会得到两个状态 $f_{p,0}$ 和 $f_{p,1}$，此时不选 $p$ 的所有方案的最大值就是 $f_{p,0}$

然后考虑选 $p$ 的情况，此时就意味着 $A_p$ 一定不能选，那么我们仍然可以按照上述的树形 $dp$ 来做，但是在 $A_p$ 这里需要特判一下，$A_p$ 只能不选。这样我们又能得到两个状态 $f_{p,0}$ 和 $f_{p,1}$，此时选 $p$ 的所有方案的最大值就是 $f_{p,1}$。

最终我们从两个情况的最大值中取一个最大值就是答案。以上就是本题的全部思路，树形 $dp$ 的时间复杂度是 $O(n)$ 的

注意，如果从每个骑士向讨厌的人连边，则整个图会是一个内向树森林，会有若干个入度为 $0$ 的段，而我们做树形 $dp$ 时是需要选择一个根节点往下递推的，因此我们建边的时候需要反向建边，建一棵外向树。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 1000010, INF = 0x3f3f3f3f;

int n;
//rm[i] 表示 i 边是否被删掉
int h[N], e[N], rm[N], w[N], ne[N], idx; //邻接表
bool st[N], ins[N]; //st 记录每个点是否被搜过，ins 记录每个点是否在栈中
//设 f[i][0] 表示以 i 为根的子树中选若干个点，且不选 i 的所有方案的最大值
//设 f[i][1] 表示以 i 为根的子树中选若干个点，且选 i 的所有方案的最大值
LL f1[N][2], f2[N][2];
LL res = 0; //记录答案

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

void dfs_f(int u, int ap, LL f[][2]) //树形 dp 求以 u 为根的子树中 u 不选 ap 的所有方案的最大值
{
    //不选 u
    for(int i = h[u]; i != -1; i = ne[i])
    {
        if(rm[i]) continue; //如果当前边已经被删，直接跳过
        int j = e[i];
        dfs_f(j, ap, f);
        f[u][0] += max(f[j][0], f[j][1]);
    }

    //选 u
    f[u][1] = -INF;
    if(u != ap) //如果 u != ap，说明 u 可以选
    {
        f[u][1] = w[u];
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] += f[j][0];
        }
    }
}

void dfs_c(int u, int from) //找出 u 所在的基环树的环
{
    st[u] = ins[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) dfs_c(j, i);
        else if(ins[j]) //找到环
        {
            rm[i] = 1; //将 u -> j 的边删掉
            dfs_f(j, -1, f1); //不选 j 的情况
            dfs_f(j, u, f2); //选 j 的情况
            res += max(f1[j][0], f2[j][1]); //累加上两种情况的最大值
        }
    }
    ins[u] = false;
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); //初始化邻接表

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

    //求出所有基环树的环
    for(int i = 1; i <= n; i++)
        if(!st[i])
            dfs_c(i, -1);

    printf("%lld\n", res);

    return 0;
}