创世纪问题

解题思路：

由于每个点可以限制另外一个点，如果我们看作从每个点向他限制的点连边，则本题就是一个基环森林。我们就是要在一个基环森林中选尽可能多的点，使得每个点都能被某一个没选中的点限制。

由于基环森林中每一棵基环树都是相互独立的，因此我们可以单独考虑每一棵基环树中最多能选择多少个点。

我们先考虑如果在一棵普通的树中如何求，一个点被限制就意味着有一个点指向它，因此就是要保证每个点的父节点都不能被选择，这样的方案我们可以用树形 $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} = \max \lbrace f_{u,0} - \max{\lbrace f_{t,0},f_{t,1} \rbrace} + f_{t,0} + 1 \rbrace~~(t \in s) \end{cases} $$

可以发现这里的树形 $dp$ 中每个点的状态是通过父节点递推过来的，因此我们需要建一个反向边，反向递推。

但是基环树是没法做树形 $dp$ 的，因此我们可以将环上某一条边断开，这样基环树就能变成一棵普通的树，就能做树形 $dp$ 了，我们取环上一点 $p$，将 $p \rightarrow A_p$ 的边断开，此时我们可以将所有方案分成两类，一类是
不用 $p \rightarrow A_p$ 这条边，这就意味着要么不选 $A_p$，要么选 $A_p$ 并且有另外一条边指向 $A_p$。此时没有用到 $p \rightarrow A_p$ 这条边，所以对 $p$ 没有任何限制，我们从 $p$ 开始求一遍树形 $dp$，最终得到两个状态 $f_{p,0}$ 和 $f_{p,1}$，由于 $p$ 选不选都行，因此这一类的答案就是这两个状态取一个最大值。

另一类是用 $p \rightarrow A_p$，这意味着我们一定要选 $A_p$，且一定不选 $p$，那么我们只需要在做树形 $dp$ 的过程中特判一下 $A_p$ 一定要选即可，最终同样得到两个状态 $f_{p,0}$ 和 $f_{p,1}$，由于 $p$ 此时一定不能选，因此这一类的答案就是 $f_{p,0}$

最终再从这两类情况的答案中取一个最大值，就是整个的答案。

注意，本题按照每个点向它限制的点连边的话，会得到一棵内向树，由于内向树有多个入度为 $0$ 的点，而树形 $dp$ 需要从一个根节点往下递归，因此这里需要建反向边，此时将 $p \rightarrow A_p$ 这条边删掉后，$p$ 就是根节点，我们就可以从 $p$ 进行递推，而前面我们分析树形 $dp$ 时也分析到需要建反向边，这里一举两得。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010, INF = 0x3f3f3f3f;

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

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

void dfs_f(int u, int ap, int f[][2]) //树形 dp 求以 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 必选，则 u 已经被 p 限制，其他子节点可选可不选
    if(u == ap) f[u][1] = f[u][0] + 1;
    else
    {
        //选 u
        f[u][1] = -INF;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            if(rm[i]) continue;
            int j = e[i];
            f[u][1] = max(f[u][1], f[u][0] - max(f[j][0], f[j][1]) + f[j][0] + 1);
        }
    }
}

void dfs_c(int u, int from) //找出所有基环树的环
{
    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; //将边 ap -> p 删去
            dfs_f(j, -1, f1); //不用边 ap -> p
            dfs_f(j, u, f2); //用边 ap -> p（必选 ap，必不选 p）
            res += max(max(f1[j][0], f1[j][1]), f2[j][0]); //累加所有方案的最大值
        }
    }
    ins[u] = false;
}

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

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

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

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

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

    return 0;
}