自动搬运

查看原文

来自洛谷，原作者为

	zac2010 a vegedog

搬运于2025-08-24 21:26:17，当前版本为作者最后更新于2023-08-31 11:12:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于每个特工只会监视一个特工，我们判断出这是一颗基环树。

基环树的题目我们往往可以从序列以及树去入手。

考虑序列怎么做。此时存在显然的贪心策略，让 $1,3,5,7,\dots$ 这些位置的特工参与行动。对这个贪心加以分析，不难把它搬到基环树上去贪心——能选 $x$，就不去放弃 $x$ 选 $a_x$。因为放弃 $x$ 一定不优于选 $x$。

但是这里还是介绍一下比较常见的 $\text{DP}$。考虑题目给出的关系是一颗树该怎么做。钦定 $f_{u,0/1}$ 为：$u$ 本身选/不选时，它的子树中最多有多少个特工参与行动。

转移：$f_{u,0}\leftarrow\max(f_{v,0},f_{v,1})$；$f_{u,1}$ 在 $f_{u,0}$ 的基础上还要避免所有子节点都参与行动的情况。

#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e6 + 10, INF = 1e9;
int n, p, ans, flag, a[N], fa[N], f[N][2];
vector<int> rt, e[N];
int find(int u){return fa[u] == u? u : fa[u] = find(fa[u]);}
void dfs(int u, int pos){
	f[u][0] = f[u][0] = 0; int mx = -INF;
	for(int &v: e[u]){
		dfs(v, pos), f[u][0] += max(f[v][0], f[v][1]);
		mx = max(mx, f[v][0] - max(f[v][0], f[v][1]));
	}
	f[u][1] = f[u][0] + (u != pos || !flag) * mx + 1;
}
int main(){
	scanf("%d", &n);
	FL(i, 1, n) fa[i] = i;
	FL(i, 1, n){
		scanf("%d", &a[i]);
		if(find(a[i]) != find(i))
			e[a[i]].emplace_back(i), fa[i] = a[i];
		else rt.emplace_back(i);
	}
	for(const int &u: rt){
		p = u, flag = 0, dfs(p, a[p]);
		int mx = max(f[p][0], f[p][1]);
		flag = 1, dfs(u, a[p]);
		ans += max(mx, f[p][0]);
	}
	printf("%d\n", ans); 
	return 0;
}