创世纪

形式化题目

有 $N$ 个点，每个点 $i$ 有一条有向出边指向 $A[i]$ ，其中 $1 \leqslant A[i] \leqslant N$ 。选出点集 $S$ ，要求对每个 $u \in S$ ，都存在 $v \notin S$ 使得 $A[v] = u$ ：

\forall u \in S,\quad \exists v \notin S:\ A[v] = u .

求 $|S|$ 的最大值。

注意约束是单向的：只对"被投放"的点提要求。没被投放的点不受任何限制，所以"一个都不投放"永远合法，答案至少是 $0$ ，题目不会无解。

由于每个点出度为 $1$ ，这张图是一个函数图：每个弱连通块恰好含有一个环，环上的点挂着若干棵内向树，整体是一片基环树森林。

以样例 $N = 6$ ， $A = [2, 3, 1, 3, 6, 5]$ 为例，箭头由 $i$ 指向 $A[i]$ ：

graph LR
    g1["1"] --> g2["2"]
    g2 --> g3["3"]
    g3 --> g1
    g4["4"] --> g3
    g5["5"] --> g6["6"]
    g6 --> g5

左边 $1 \to 2 \to 3 \to 1$ 是一个三元环，点 $4$ 挂在 $3$ 下面；右边 $5 \leftrightarrow 6$ 是一个二元环。两个连通块彼此独立，把各自的最优值加起来就是答案。

正解

思路

第一步：把条件翻译成"孩子"的语言。

把边反向，记 $\mathrm{children}(u) = \{\,v : A[v] = u\,\}$ ，也就是"所有能限制 $u$ 的点"。那么题目的条件等价于

u \in S \;\Longrightarrow\; \mathrm{children}(u) \nsubseteq S ,

即： $u$ 一旦被选，它的孩子里至少有一个不能被选。

第二步：先做树。 环外的点构成以环上点为根的内向树。对树上的点 $v$ ，设父节点 $p = A[v]$ （ $v$ 是 $p$ 的一个孩子）。我们只关心两个数：

记号	含义
$\mathrm{off}[v]$	$v$ 不投放时， $v$ 的子树（不含 $v$ ）最多能投放多少个
$\mathrm{gain}[v]$	在 $v$ 的孩子里挑一个不投放，所牺牲的最小值；没有孩子时记为 $\infty$

子树各自独立， $v$ 不投放时孩子 $c$ 可以自由地取它的最优值，于是 $\mathrm{off}[v] = \sum_c \mathrm{best}[c]$ 。若为了让 $v$ 投放而必须牺牲某个孩子 $c$ ，就要把 $c$ 从"最优"压回"不投放"。这个损失是

\mathrm{slack}[c] = \max\bigl(0,\ 1 - \mathrm{gain}[c]\bigr),

取 $\mathrm{gain}[v] = \min_c \mathrm{slack}[c]$ 损失最小——因为 $v$ 投放只需要一个孩子不投放。 gain 的取值只可能是 $0$ 、 $1$ 两档（ $\mathrm{slack} \leqslant 1$ ），代码里用 $2$ 表示“没有孩子”。 $\mathrm{slack}$ 里那个 $\max(0, \cdot)$ 是减免：如果 $c$ 本来就已经没被投放，那逼它不投放不花任何代价。

于是对 $v$ 自身：

v \notin S \Rightarrow \mathrm{off}[v], \qquad v \in S \Rightarrow \mathrm{off}[v] + 1 - \mathrm{gain}[v].

这一步实现时不必显式建树：用入度做拓扑排序（剥叶子）自底向上汇总即可，剥完还剩下入度非 $0$ 的点就正好是环上的点。

第三步：再做环。 环上点 $v$ 的限制者分两类——环上的那个孩子，和挂在它下面的整棵树。把环按"孩子在前、父亲在后"排成 $\mathrm{ring}[0..k-1]$ ，即 $A[\mathrm{ring}[i]] = \mathrm{ring}[i-1]$ ，环尾 $\mathrm{ring}[k-1]$ 是环首 $\mathrm{ring}[0]$ 的限制者。

只要枚举环尾是否投放这两种情况，环就断成一条链，链上相邻两点之间是一条真实的限制关系，可以线性 DP 扫完。用 $dp_0, dp_1$ 表示"刚处理的点不投放 / 投放"的最优值，它同时就是下一个点的限制者，转移为：

新状态	取值	说明
$dp_0'$	$\max(dp_0, dp_1) + \mathrm{off}[v]$	$v$ 不投放，对孩子无要求
$dp_1'$	$\max(dp_0,\ dp_1 - \mathrm{gain}[v]) + \mathrm{off}[v] + 1$	$v$ 投放，见证来自环上前驱 $dp_0$ ，或改让挂树孩子不投放

两种环尾状态分别给环首定下不同的初值，并在链尾取对应的那一维：

环尾	环首 $dp_0, dp_1$	链尾取
不投放	$\mathrm{off}[r_0],\ \mathrm{off}[r_0]+1$ （可以拿环尾当见证）	$dp_0$
投放	$\mathrm{off}[r_0],\ \mathrm{off}[r_0]+1-\mathrm{gain}[r_0]$ （只能靠挂树）	$dp_1$

长度为 $1$ 的自环要单独处理：唯一的环上候选就是自己，不能拿自己当见证，答案是 $\max(\mathrm{off}[v],\ \mathrm{off}[v]+1-\mathrm{gain}[v])$ 。

用样例走一遍。 点 $4$ 没有任何孩子（没人指向它），所以它永远不能投放，它给 $\mathrm{off}[3]$ 的贡献是 $0$ ，并且让 $\mathrm{gain}[3] = 0$ 。对环 $\{1,2,3\}$ ：若环尾 $3$ 不投放，可取 $\{2,3\}$ 两个（ $2$ 由 $1$ 见证， $3$ 由 $4$ 见证，但 $4$ 不在 $S$ 里）——这正是 $dp_0 = 2$ ；若环尾 $3$ 投放， $1$ 就失去见证者，只能取 $1$ 个。另一块 $\{5,6\}$ 只能取 $1$ 个。合计 $2 + 1 = 3$ 。

复杂度。 每个点进出栈一次、环上每个点被扫两次，时间 $O(N)$ ，空间 $O(N)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 基环树森林：剥掉挂树后每个环单独 DP，求最多能投放多少个元素
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

const ll NEG = -(1LL << 50); // 非法状态；合法值恒为非负
const int NO_CHILD = 2;      // gain 的初值：没有孩子就付不出“牺牲”

int n;
vector<int> parent; // parent[u] 就是题面的 A[u]
vector<int> indeg;  // 入度 = 孩子个数；> 0 表示落在某个环上
vector<int> off;    // off[v]：v 不投放时，v 的子树（不含 v）最多能投放多少个
vector<int> gain;   // gain[v]：逼 v 的某个孩子不投放所需的最小牺牲

// 剥掉所有不在环上的点，自底向上把每棵挂树压成两个数
void peel_trees() {
    indeg.assign(n + 1, 0);
    for (int v = 1; v <= n; v++) {
        indeg[parent[v]]++;
    }
    off.assign(n + 1, 0);
    gain.assign(n + 1, NO_CHILD);
    vector<int> stk;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) {
            stk.push_back(v); // 环外的叶子先入栈
        }
    }
    while (!stk.empty()) {
        int v = stk.back();
        stk.pop_back();
        int slack = (gain[v] >= 1) ? 0 : 1 - gain[v]; // 孩子本来未必投放，牺牲可以减免
        int p = parent[v];
        off[p] += off[v] + slack;
        if (slack < gain[p]) {
            gain[p] = slack;
        }
        indeg[p]--;
        if (indeg[p] == 0) {
            stk.push_back(p);
        }
    }
}

// 一个环最多能投放多少个；ring 按「孩子在前、父亲在后」排列
ll ring_best(const vector<int>& ring) {
    int head = ring[0];
    ll on_tree = (gain[head] < NO_CHILD) ? (ll)off[head] + 1 - gain[head] : NEG;
    if ((int)ring.size() == 1) { // 自环：唯一的环上候选是自己，不能当见证
        return off[head] > on_tree ? off[head] : on_tree;
    }
    ll best = NEG;
    for (int tail_off = 1; tail_off >= 0; tail_off--) {
        ll dp0 = off[head];
        ll dp1 = tail_off ? (ll)off[head] + 1 : on_tree;
        for (int t = 1; t < (int)ring.size(); t++) {
            int v = ring[t];
            ll free_choice = dp0 > dp1 ? dp0 : dp1; // 环上前驱不投放，v 才可以投放
            ll by_tree = (gain[v] < NO_CHILD) ? dp1 - gain[v] : NEG;
            ll best_pred = dp0 > by_tree ? dp0 : by_tree;
            dp1 = (ll)off[v] + 1 + best_pred;
            dp0 = free_choice + off[v]; // v 不投放，挂树各自取最优
        }
        ll cur = tail_off ? dp0 : dp1; // 环尾不投放取 dp0，投放取 dp1
        if (cur > best) {
            best = cur;
        }
    }
    return best;
}

int main() {
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    parent.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &parent[i]);
    }
    peel_trees();

    ll total = 0;
    for (int s = 1; s <= n; s++) {
        if (indeg[s] == 0) {
            continue; // 已被剥掉，贡献早已算进它所属的环
        }
        vector<int> ring;
        int u = s;
        while (indeg[u] > 0) { // 顺着 parent 走，孩子总在父亲前面
            ring.push_back(u);
            indeg[u] = 0; // 打标记，免得同一个环被走第二遍
            u = parent[u];
        }
        total += ring_best(ring);
    }
    printf("%lld\n", total);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 00:34
# update_at: 2026-10-02 00:56

import sys
from array import array
from itertools import chain

NEG = -(1 << 50)  # 非法状态；合法值恒为非负
NO_CHILD = 2      # gain 的初值：没有孩子就付不出"牺牲"，且 max(0, 1 - 2) = 0 正好等价于无穷大


def peel_trees(parent: array, n: int) -> tuple[array, array, array]:
    """剥掉所有不在环上的点，自底向上把每棵挂树压成两个数。

    parent[u] 就是题面的 A[u]；u 的见证者集合恰好是 parent 为 u 的那些点。
    off[v]   v 不投放时，v 的子树（不含 v）最多能投放多少个
    gain[v]  逼 v 的某个孩子不投放所需的最小牺牲，没有孩子时是 NO_CHILD
    返回的 indeg[v] > 0 表示 v 剥不掉，也就是落在某个环上。
    """
    indeg = array('i', bytes(4 * (n + 1)))
    for v in range(1, n + 1):
        indeg[parent[v]] += 1                       # 入度正是 v 的孩子个数
    off = array('i', bytes(4 * (n + 1)))
    gain = array('b', bytes([NO_CHILD]) * (n + 1))
    stack = [v for v in range(1, n + 1) if indeg[v] == 0]  # 环外的叶子先入栈

    while stack:
        v = stack.pop()
        slack = 0 if gain[v] >= 1 else 1 - gain[v]  # 孩子本来未必投放，牺牲可以减免
        p = parent[v]
        off[p] += off[v] + slack
        if slack < gain[p]:
            gain[p] = slack
        indeg[p] -= 1
        if indeg[p] == 0:                           # 孩子都处理完了，v 也成了叶子
            stack.append(p)

    return indeg, off, gain


def ring_best(ring: list[int], off: array, gain: array) -> int:
    """一个环最多能投放多少个。ring 按“孩子在前、父亲在后”排列。

    于是 A[ring[i]] = ring[i-1]：轮到 ring[i] 时，它在环上的见证者 ring[i-1] 已经定好，
    dp0 / dp1 就是“ring[i] 不投放 / 投放”的最优值。环尾 ring[-1] 是环首 ring[0] 的
    见证者，故枚举环尾状态两次，让环首取到对应的初值，并在链尾取回对应的一维。
    """
    head = ring[0]
    on_tree = off[head] + 1 - gain[head] if gain[head] < NO_CHILD else NEG  # 只靠挂树当见证
    if len(ring) == 1:                              # 自环：唯一的环上候选是自己，不能当见证
        return off[head] if off[head] > on_tree else on_tree

    best = NEG
    for tail_off in (True, False):
        dp0 = off[head]
        dp1 = off[head] + 1 if tail_off else on_tree
        for v in ring[1:]:
            free = dp0 if dp0 > dp1 else dp1         # 环上前驱不投放，v 才可以投放
            by_tree = dp1 - gain[v] if gain[v] < NO_CHILD else NEG
            dp1 = off[v] + 1 + (dp0 if dp0 > by_tree else by_tree)
            dp0 = free + off[v]                      # v 不投放，挂树各自取最优
        cur = dp0 if tail_off else dp1               # 环尾不投放取 dp0，投放取 dp1
        if cur > best:
            best = cur
    return best


def best_total(parent: array, n: int) -> int:
    """整片基环树森林最多能投放多少个元素。"""
    indeg, off, gain = peel_trees(parent, n)
    total = 0
    for s in range(1, n + 1):
        if indeg[s] == 0:                            # 已被剥掉，贡献早已算进它所属的环
            continue
        ring: list[int] = []
        u = s
        while indeg[u] > 0:                          # 顺着 parent 走，孩子总在父亲前面
            ring.append(u)
            indeg[u] = 0                             # 打标记，免得同一个环被走第二遍
            u = parent[u]
        total += ring_best(ring, off, gain)
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                                   # 第一行是元素个数
    parent = array('i', chain([0], data))            # 用 0 占位，使 A[i] 落在下标 i
    sys.stdout.write(str(best_total(parent, n)) + "\n")


if __name__ == "__main__":
    solve()

复杂度

时间 $O(N)$ ，空间 $O(N)$ 。整份实现全部迭代，不含递归， $N = 10^6$ 也可安全运行。

实现上有一点需要留意： $N$ 到 $10^6$ 时，四个 Python list[int] 会占掉约 160MB，超过本题 128MB 的限制。因此 parent、indeg、off 用 array('i')（32 位整型）， gain 只取 $0/1/2$ 三档故用 array('b')，把峰值压到约 85MB。

总结

这道题的难点不在 DP 本身，而在看出图的结构：每个点出度为 $1$ ，所以是基环树森林。之后把它拆成两件事——环外的挂树可以自底向上一次算完，环上只需要枚举环尾一个点的状态就能断开成链。整个过程中最关键的观察是" $u$ 投放只需要一个孩子不投放"，它把指数级的组合选择压缩成 $\min_c \mathrm{slack}[c]$ 一个数。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8
9输入: 每个点一条出边 i -> A[i]
`- 每个弱连通块恰好一个环  =>  基环树森林
   |- 环外的挂树: 自底向上剥叶子
   |  |- off[v] = Σ (off[c] + slack[c])        v 不投放
   |  `- gain[v] = min slack[c]                逼一个孩子不投放的最小牺牲
   `- 环上: 枚举环尾投放 / 不投放两种, 环断成链
      |- dp0' = max(dp0, dp1) + off[v]
      `- dp1' = max(dp0, dp1 - gain[v]) + off[v] + 1
         `- 各连通块最优值相加 = 答案

顺着读：函数图决定了"一个环 + 若干挂树"的结构；挂树只向环上传两个数 $\mathrm{off}$ 和 $\mathrm{gain}$ ；环上因为首尾相连才需要枚举一个点的状态来断环；断环后就是普通的链上 DP，逐块求和即得答案。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析