第一道模拟赛场切的紫题。

思路

$n$ 个人，每个人选一个人开枪，形成若干棵基环树，我们可以对于每课基环树分开考虑，最后把答案加起来。

最大值

先考虑求最大值，即求最后没有被杀的最小人数。对于树上和环上分开考虑：

• 树：显然只有叶子节点不可能被杀。

• 环：最后一定至少有一个人没有被杀。

然后我们考虑基环树上的情况，如果该基环树每个点都在环上，那么至少有一个人没有被杀，否则最后没有被杀的人至少为叶节点总数。

最小值

设环上的一个点 $u$。一个显然的想法是对于以 $u$ 为根的子树做树形 dp，求出 $u$ 被杀和不被杀时 $u$ 子树内被杀人数的最小值（只考虑 $u$ 的儿子把他杀了，不考虑环上其他人杀了他）。然后我们在环上做一个 dp，求出答案。

树形 dp

用 $dp_{u,0/1}$ 表示 $u$ 被杀 / 没有被杀 时以 $u$ 为根的子树中被杀的最小人数，转移（$v$ 为 $u$ 儿子）：

• $dp_{u,0} \leftarrow \min(dp_{v,0},dp_{v,1})$（$v$ 可以在他被杀前先杀了 $u$）

• $dp_{u,1} \leftarrow dp_{v,0}$

注意初始值，不可能被杀或必须被杀时相应的 $dp$ 值赋为 $n+1$，$dp_{u,0}$ 初值为 $1$。

注意 $dp$ 数组要开 long long，如果不想开可以特判 $dp$ 值为 $n+1$ 的情况。然后一定要特判掉自环。

环上 dp

与树形 dp 相似。

设 $f_{i,0/1}$ 表示环上第 $i$ 个人 被杀 / 没有被杀 时被杀的最小人数，转移：

• $f_{i,0} = \min(f_{i-1,0},f_{i-1,1})+\min(dp_{i,0},dp_{i,1}+1)$

• $f_{i,1} = f_{i-1,0}+dp_{i,1}$

但考虑到第一个人可能没有儿子，导致 $dp_{1,0}=n+1$，所以我们可以对于第一个人和第二个人分别做两次 dp（对于第一个人和第二个人分别求他们被杀和不被杀时的答案），最终答案取最小值。

优化

然后这题卡空间。 我们可以先把环上 dp 的 $f$ 数组滚掉，用变量写就行了。然后我们使用神秘的 lambda 语法（详见代码），开 c++23 就过了。

代码

::::info[]

#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back
using namespace std;

const int maxn = 1e6 + 5;

int n, p[maxn], mn, mx, cnt;

vector <int> e[maxn];

int tot, cyc[maxn];

bool vis[maxn], oncyc[maxn];

ll dp[maxn][2]; // 这个人 死 / 活 时死的最少人数 

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
		e[p[i]].eb(i);
	}
	
	auto dfs = [&](auto &&self, int x) -> void {
		vis[x] = 1;
		dp[x][0] = 1;
		if(!e[x].size()) cnt++, dp[x][0] = n + 1;
		if(oncyc[x] && e[x].size() == 1 && e[x][0] != x) dp[x][0] = n + 1;
		for(int y : e[x]) {
			if(oncyc[y]) continue;
			self(self, y);
			dp[x][1] += dp[y][0];
			dp[x][0] += min(dp[y][0], dp[y][1]);
		}
		return;
	};
	
	auto calc = [&](int s, bool flag) -> int {
		int f0 = n + 1, f1 = n + 1;
		for(int i = s; i < s + tot; i++) {
			int x = cyc[i];
			if(i == s) {
				if(flag) f1 = dp[x][1];
				else f0 = dp[x][0];
			}
			else {
				int t0 = min(f0, f1) + min(dp[x][0], dp[x][1] + 1);
				int t1 = f0 + dp[x][1];
				f0 = t0, f1 = t1;
			}
		}
		if(flag) return f0;
		return min(f0, f1);
	};
	
	for(int i = 1; i <= n; i++) {
		if(vis[i]) continue;
		int u = i;
		while(!vis[u]) {
			vis[u] = 1;
			u = p[u];
		}
		tot = 0;
		int v = u;
		do {
			oncyc[v] = 1;
			cyc[++tot] = v;
			v = p[v];
		} while(v != u);
		cnt = 0;
		for(int j = 1; j <= tot; j++) dfs(dfs, cyc[j]);
		if(tot > 1) mx += max(1, cnt);
		else mx += cnt;
		cyc[tot + 1] = cyc[1];
		mn += min(min(calc(1, 0), calc(1, 1)), min(calc(2, 0), calc(2, 1)));
	}
	cout << mn << " " << n - mx << "\n";
	return 0;
} // lambda

::::