[EC Final 2022] Coloring

形式化题目

给出 $n$ 个点，点 $i$ 有权值 $w_i$ ，并给出一条有向边 $i \to a_i$ （ $a_i \neq i$ ）。初始只有 $s$ 的颜色 $c_s = 1$ ，其余 $c_i = 0$ 。

可以任意多次执行操作：选一个 $i$ ，令 $c_i \leftarrow c_{a_i}$ ，代价 $p_i$ 。

最终得分是「颜色为 $1$ 的点的权值和」减去「所有操作的代价和」。求最大得分。

由于每个点恰好有一条出边，把 $a_i \to i$ 反过来看，整张图是若干棵外向基环树（每个连通块恰好一个环，环外结点指向环）。所有操作都只是「把父亲 $a_i$ 当前的 0/1 复制给自己」，信息沿着 $a$ 的方向（即沿着反图的父子方向）向下流动。

正解

思路

第一步：把「操作序列」翻译成每个点被改色的次数。

设 $c_u$ 表示点 $u$ 被操作的次数（即它被改色多少次）。有两个关键性质：

颜色由次数的奇偶性决定。 初始时只有 $s$ 是 $1$ ，其余是 $0$ 。点 $u$ 每被改一次颜色就翻转一次，所以最终颜色为
$\text{color}(u) = (c_u + [u = s]) \bmod 2 .$
于是点 $u$ 贡献的权值是 $(c_u + [u=s])\bmod 2$ 为 $1$ 时的 $w_u$ ，否则为 $0$ 。
相邻两次改色之间必须有颜色可复制，因此次数受父亲限制。 点 $u$ 的第 $k$ 次改色，是把此刻 $a_u$ 的颜色复制过来，所以 $u$ 不可能比 $a_u$ 被改得更多次：要有第 $k$ 次改色的机会，就得先有 $a_u$ 的颜色变化。形式化地：
$c_u \leqslant c_{a_u} + [a_u = s] \qquad (u \neq s).$
其中 $+[a_u = s]$ 是因为根 $s$ 一开始就持有颜色 $1$ ，相当于白送一次。

根 $s$ 不受这条约束（没有「更上层」的点能限制它）。

第二步：为什么总操作次数就是 $\sum c_u$ 。 我们只在颜色确实会改变时才做操作；连续两次把同一个点写成同一种颜色是纯浪费，可以直接删掉。所以任何有意义的方案都对应一组满足上面约束的 $c_u$ ，代价恰好是 $\sum c_u p_u$ ；反之给定一组合法 $c_u$ ，按从外层到内层的顺序执行各点的改色也能把方案构造出来。于是问题等价于：

\max \sum_{u} \Big( \big(c_u + [u=s]\big)\bmod 2 \Big) w_u - \sum_u c_u p_u, \quad \text{s.t. } c_u \leqslant c_{a_u} + [a_u = s]\ (u \neq s).

这是一个在基环树上做选择的 DP。注意 $c_u$ 只需要枚举到 $n$ （超过 $n$ 次改色没有意义，因为 $2^n$ 之外的翻转不会带来新收益、只会增加代价）。

第三步： $s$ 不在环上时——纯树形 DP。

此时从 $s$ 出发顺着 $a$ 走永远走不到环（ $s$ 在某个「尾巴」上），我们干脆反过来，把 $a_i \to i$ 看成以 $s$ 为根的外向树，做经典树形 DP：

设 $f_{u,i}$ 表示「点 $u$ 被改色 $i$ 次时， $u$ 的子树能得到的最大收益」。初值由第一步的公式直接给出：

f_{u,i} = \Big( (i + [u=s]) \bmod 2 \Big) w_u - i\, p_u .

转移时对每个儿子 $v$ 合并。设 $v$ 被改色 $j$ 次，由约束 $c_v \leqslant c_u + [u = s]$ 得 $j \leqslant i + [u=s]$ ，所以

f_{u,i} \leftarrow f_{u,i} + \max_{0 \leqslant j \leqslant i + [u=s]} f_{v,j}.

对 $f_{v,\cdot}$ 做前缀最大值，就能在 $O(1)$ 内取到这个 $\max$ ，合并一个儿子的代价是 $O(n)$ 。

答案是在根处取 $\max_{i} f_{s,i}$ 。这里还有一个化简：可以证明答案就是 $\max\{f_{s,0}, f_{s,1}\}$ 。直观上， $s$ 每多改一次色都要花钱，而它下面的点至多比它多改一次； $c_s \geqslant 2$ 时把 $s$ 的那两轮零一翻转删掉，子树约束只会变松、代价只会变小。因此树的情况只用看 $i = 0, 1$ 两个值。

第四步： $s$ 在环上时——环上再套一层 DP。

先找出 $s$ 所在的环 $\mathrm{cyc}_1 = s,\ \mathrm{cyc}_2,\ \dots,\mathrm{cyc}_k$ （环上的边方向是 $\mathrm{cyc}_i \to \mathrm{cyc}_{i+1}$ ）。

对环上每个点先把它环外的子树用上面的树形 DP 合并进 $f$ （环上的儿子由环 DP 负责，跳过）。

环长 $k = 2$ ： 环上只有 $s$ 和 $t$ 两个点。此时枚举 $c_s, c_t \in \{0,1\}$ 的三种可行组合即可，答案为
$\max\{f_{s,0}+f_{t,0},\ f_{s,0}+f_{t,1},\ f_{s,1}+f_{t,0}\}.$
环长 $k > 2$ ： 环上相邻两个点的次数差至多为 $1$ ：一旦 $c_{\mathrm{cyc}_{i+1}} \geqslant c_{\mathrm{cyc}_i} + 2$ ， $\mathrm{cyc}_{i+1}$ 的第 $c$ 次改色就取不到颜色（它的父亲还没改那么多次），所以非法；而沿着环走一圈最多让次数每次增加 $1$ 。于是枚举 $c_s = r$ （注意把 $s$ 自带的初始颜色也算进 $c_s$ ，所以 $r \geqslant 1$ ），用

$g_{i,j} = \text{走到环上第 } i \text{ 个点、且 } c_{\mathrm{cyc}_i} = r - j \text{ 时的最大收益} \qquad (j = 0,1,2)$
来转移。初始 $g_{1,0} = f_{s,r-1}$ （ $-1$ 是因为 $c_s$ 的计数里额外含了初始的那一次颜色）， $g_{1,1} = g_{1,2} = -\infty$ 。对 $i > 1$ ：

$g_{i,j} = f_{\mathrm{cyc}_i,\,r-j} + \max_{0 \leqslant k' \leqslant j} g_{i-1,k'}.$
最后对所有 $r$ 取 $\max_j g_{k,j}$ 的最大值。

这份 $j \leqslant 2$ 的枚举是完备的：沿环走一圈，次数最多比 $s$ 少 $2$ （把 $s$ 的初始颜色 1 沿着环推一圈再推回来的构造可以达到这个差值），再少就不合法了。

状态转移示例。 以样例一（ $n=3$ ， $a = [3,1,2]$ ，即 $1 \to 3 \to 2 \to 1$ ，环长 $3$ ， $s=1$ ）为例，环上每点的子树都是空的， $f_{u,i} = ((i+[u=s]) \bmod 2) w_u - i\,p_u$ ：

$i$	$f_{1,i}$ （ $w_1=-1,p_1=1$ ）	$f_{2,i}$ （ $w_2=-1,p_2=0$ ）	$f_{3,i}$ （ $w_3=2,p_3=0$ ）
0	$-0=0$	$0$	$0$
1	$0-1=-1$	$w_2=-1$	$w_3=2$
2	$w_1-2=-3$	$0$	$0$

取 $r = 2$ （即 $c_1 = 1$ ， $c_2 = c_3 = 0$ ）： $g_{1,0} = f_{1,1} = -1$ ；走到点 $2$ 时 $c_2 = r-2 = 0$ ，得 $-1 + f_{2,0} = -1$ ；走到点 $3$ 时 $c_3 = 0$ ，得 $-1 + f_{3,0} = -1$ 。另一条 $r$ 取法给出 $f_{3,1} = 2$ 减去代价，最终答案 $1$ ，与样例一致。

代码

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143/**
 * 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 15:23
 * update_at: 2026-10-03 12:30
 *
 * P9716 [EC Final 2022] Coloring
 *
 * 模型：把操作 c_i <- c_{a_i} 看成"把 i 的父亲 a_i 的颜色复制给 i"。
 * 对每个点 u 记 c_u = 它被操作(改色)的次数，则：
 *   - u 最终颜色 = (c_u + [u == s]) % 2，因为初始只有 s 是 1；
 *   - 要第 k 次改色 u，必须先有颜色从 a_u 流过来，所以 c_u 与 c_{a_u} 满足
 *     c_u <= c_{a_u} + [a_u == s]（u != s），根 s 不受这条约束；
 *   - 总代价 = sum c_u * p_u（同一颜色连续写两次无意义，所以总次数就是 c_u）。
 * 于是题目变成：在基环树上按上面的约束选 c_u，最大化
 *   sum_{u: 最终颜色=1} w_u - sum c_u * p_u
 *
 * 做法：先找 s 所在的环。
 *   - s 不在环上：把 a_i -> i 看成以 s 为根的外向树，树形 DP
 *     f[u][i] = u 被改色 i 次时 u 子树的最大收益，转移用前缀 max 优化。
 *     答案 = max(f[s][0], f[s][1])（改色超过 1 次不会更优）。
 *   - s 在环上（环长 k）：环上点的子树各自树形 DP，环上再套一层 DP。
 *     k == 2 时只有三种合法组合，直接取 max。
 *     k > 2 时枚举 c_s = r，用 g[i][j] (j = 0/1/2) 表示走到环上第 i 个点时
 *     它的改色次数是 r - j。相邻两点的次数最多相差 1（循环一次）。
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 5005;
const ll NEG = -(ll)4e18;      // 负无穷，注意别让它参加加法后溢出

int n, s;                      // 点数，初始颜色为 1 的点（输入 1 下标，代码里转 0 下标）
ll w[MAXN], p[MAXN];           // 价值、单次改色代价
int a[MAXN];                   // a[i] 指向的元素
vector<int> g[MAXN];           // 反图 a_i -> i，即以 i 为父亲的儿子集合

int on_cycle[MAXN];            // 是否属于 s 所在的环
vector<int> cyc;               // s 所在的环（rot 成以 s 开头）

ll f[MAXN][MAXN];              // f[u][i]: u 被改色 i 次时，u 子树的最大收益

// 计算 u 子树（u 在环上或树上，环上结点的环上儿子被跳过）
void dfs(int u) {
    // 基础值：u 最终颜色 = (i + [u == s]) % 2，产生价值 w[u]；代价 i * p[u]
    for (int i = 0; i <= n; i++) {
        int color = (i + (u == s)) & 1;
        f[u][i] = (color ? w[u] : 0) - (ll)i * p[u];
    }
    f[u][n + 1] = NEG;

    for (int v : g[u]) {
        if (on_cycle[v]) continue;      // 环上的儿子由环 DP 负责
        dfs(v);
        ll best = NEG;                  // 前缀 max：max_{0 <= j <= i} f[v][j]
        for (int i = 0; i <= n; i++) {
            best = max(best, f[v][i]);
            ll add = best;
            // 父亲是 s 时，儿子可以多用一次：j <= i + 1
            if (u == s) add = max(add, f[v][i + 1]);
            f[u][i] += add;
        }
    }
}

// 找到 s 所在环上的所有点
void find_cycle() {
    int x = s;
    vector<char> vis(n, 0);
    while (!vis[x]) { vis[x] = 1; x = a[x]; }
    vector<char> used(n, 0);
    int y = x;
    while (!used[y]) { cyc.push_back(y); used[y] = 1; y = a[y]; }
    reverse(cyc.begin(), cyc.end());
    for (int u : cyc) on_cycle[u] = 1;
    // 旋转成以 s 开头
    int pos = 0;
    for (int i = 0; i < (int)cyc.size(); i++) if (cyc[i] == s) pos = i;
    rotate(cyc.begin(), cyc.begin() + pos, cyc.end());
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    s--;                                    // 转成 0 下标
    for (int i = 0; i < n; i++) cin >> w[i];
    for (int i = 0; i < n; i++) cin >> p[i];
    for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; }

    for (int i = 0; i < n; i++) g[a[i]].push_back(i);

    find_cycle();

    if (!on_cycle[s]) {
        // s 不在环上：s 为根的树，直接树形 DP
        dfs(s);
        cout << max(f[s][0], f[s][1]) << "\n";
        return 0;
    }

    // s 在环上：环上每个点跑一遍子树 DP
    for (int u : cyc) dfs(u);

    int k = (int)cyc.size();
    if (k == 2) {
        // 只有 s 和 t 两个点，枚举它们的改色次数组合
        int t = cyc[1];
        ll ans = max(f[s][0] + f[t][0], f[s][0] + f[t][1]);
        ans = max(ans, f[s][1] + f[t][0]);
        cout << ans << "\n";
        return 0;
    }

    // k > 2：枚举 c_s = r（把 s 的初始颜色 1 也算进去，所以 r >= 1）
    ll ans = NEG;
    for (int r = 1; r <= n + 1; r++) {
        // g[j]: 当前环上点改色次数为 r - j 时的最大收益
        ll g[3] = {f[s][r - 1], NEG, NEG};
        for (int i = 1; i < k; i++) {
            ll ng[3] = {NEG, NEG, NEG};
            // 本点次数 = r：前一个点次数只能也是 r
            if (g[0] > NEG / 2) ng[0] = max(ng[0], g[0] + f[cyc[i]][r]);
            // 本点次数 = r-1：前一个点是 r 或 r-1
            {
                ll pre = max(g[0], g[1]);
                if (pre > NEG / 2) ng[1] = max(ng[1], pre + f[cyc[i]][r - 1]);
            }
            // 本点次数 = r-2：前一个点可以是 r / r-1 / r-2
            if (r > 1) {
                ll pre = max(max(g[0], g[1]), g[2]);
                if (pre > NEG / 2) ng[2] = max(ng[2], pre + f[cyc[i]][r - 2]);
            }
            g[0] = ng[0]; g[1] = ng[1]; g[2] = ng[2];
        }
        ans = max(ans, max(max(g[0], g[1]), g[2]));
    }
    cout << ans << "\n";
    return 0;
}

代码里的实现要点：

on_cycle[u] 标记 $s$ 所在环上的点；dfs(u) 跳过环上的儿子，避免在环上递归。
f[u][i] 的下标 $i$ 开到 $n+1$ ，因为合并环上/树上儿子时需要访问 $f_{v, i+1}$ ，多开一格并置为 $-\infty$ 。
找环时从 $s$ 出发沿 $a$ 走，先用 vis 找到第一个重复出现的点，再从它绕一圈，得到的就是 $s$ 所在环（对不连通的功能图也成立，与题面的基环树连通性无关）。

复杂度

树上部分：每个点对每个 $i \in [0,n]$ 做一次 $O(1)$ 的前缀 $\max$ 合并，共 $O(n^2)$ 。
环上部分：枚举 $r$ 共 $O(n)$ 种，每种沿环走 $O(k) \leqslant O(n)$ 步、每步 $O(1)$ ，总计 $O(n^2)$ 。
总时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ （ $n = 5\times10^3$ 时约 $200$ MB，限制为 $1$ GB）。

总结

关键在于把「一串操作」重新解释成每个点的改色次数 $c_u$ ：颜色只看 $c_u$ 的奇偶，代价是 $\sum c_u p_u$ ，而操作可行性被压成了一条简单的局部约束 $c_u \leqslant c_{a_u} + [a_u = s]$ 。
有了这个模型，问题就归约成基环树上的 DP： $s$ 不在环上时是普通树形 DP，用前缀 $\max$ 把合并降到 $O(n^2)$ ； $s$ 在环上时先对每个环上点跑子树 DP，再在环上枚举 $c_s$ ，用「相邻次数差 $\leqslant 1$ 」做长度为 $3$ 的环上 DP。
边界情况主要有三类：环长为 $2$ 需要单独枚举；结点权值可为负，所以「不选点」是合法选择（ $f_{u,\cdot}$ 的初值里颜色为 $0$ 时贡献 $0$ ）；答案可能为负，不能用 $0$ 初始化。

[EC Final 2022] Coloring

目录

形式化题目

正解

思路

代码

复杂度

总结