NOIP-模拟赛第3场 题解

T1 循环乐段（melody）

简要题意

每组给出 $N$ 个取值为 $1\sim K$ 的音符，$3\le N\le99999$ 且 $3\mid N$，$1\le K\le10^5$。允许改写任意位置，求至少修改多少个位置，才能得到同一个三音符片段反复连接的序列；片段内允许音符相同，也允许零次修改。至多 $10$ 组，$\sum N,\sum K\le3\times10^5$，逐组输出最小修改数。

一句话题解

按位置对 $3$ 取模分成三类，每类保留出现次数最多的音符，修改其余位置。

完整题解

20 分：固定目标

测试点 $1\sim4$ 保证 $1,2,3$ 反复连接是一种最优结果。直接与该序列比较，数出不同的位置，时间 $O(N)$、额外空间 $O(1)$。其他测试点不作这个保证，不能把“常见的三个音符”当成最优片段。

#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		int n, k, ans = 0;
		cin >> n >> k;
		for (int i = 0; i < n; i ++) {
			int x;
			cin >> x;
			ans += x != i % 3 + 1;
		}
		cout << ans << "\n";
	}
	return 0;
}

50 分：小规模枚举与特殊性质结合

在 $N,K\le30$ 的测试点 $5\sim10$，枚举目标片段的三个音符，共 $K^3$ 种，每次扫描整个原序列求修改数，取最小值。时间 $O(NK^3)$、空间 $O(N)$。由于三个音符允许相同，枚举时不能跳过相同值。

小规模时枚举，其他输入与固定目标比较，即可兼得前两档的 50 分。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, a[N], p[3];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		int ans = 0;
		for (int i = 0; i < n; i ++) {
			cin >> a[i];
			ans += a[i] != i % 3 + 1;
		}
		if (n <= 30 && k <= 30) {
			ans = n;
			for (p[0] = 1; p[0] <= k; p[0] ++)
				for (p[1] = 1; p[1] <= k; p[1] ++)
					for (p[2] = 1; p[2] <= k; p[2] ++) {
						int res = 0;
						for (int i = 0; i < n; i ++) res += a[i] != p[i % 3];
						ans = min(ans, res);
					}
		}
		cout << ans << "\n";
	}
	return 0;
}

满分：分类独立优化

使用从 $0$ 开始的位置编号，令 $cnt[r][v]$ 表示满足 $i\bmod3=r$ 且音符为 $v$ 的位置数。

如果目标片段的第 $r$ 个音符选为 $v$，这一类恰能保留 $cnt[r][v]$ 个位置。因为不同类之间没有“音符必须不同”等约束，三类可以独立选择。因此

$$ans=N-\sum_{r=0}^{2}\max_{1\le v\le K}cnt[r][v].$$

这既是下界也是可行方案：任意结果在第 $r$ 类最多保留该类的众数频次；分别选取三个众数，就能同时达到三个上界。

每组时间 $O(N+K)$、空间 $O(K)$。将三类分别排序并求最长相等段的 $O(N\log N)$ 做法同样可以获得满分。答案不超过 $N$，使用 int 即可；多组数据需要清空本组可能用到的全部计数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, k, cnt[3][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 0; i < 3; i ++) memset(cnt[i], 0, (k + 1) * sizeof(int));
		for (int i = 0; i < n; i ++) {
			int x;
			cin >> x;
			cnt[i % 3][x] ++;
		}
		int ans = n;
		for (int i = 0; i < 3; i ++) {
			int mx = 0;
			for (int j = 1; j <= k; j ++) mx = max(mx, cnt[i][j]);
			ans -= mx;
		}
		cout << ans << "\n";
	}
	return 0;
}

容易误判的方向

• 固定第一组三音符：第一段不一定具有代表性。例如 $4,4,4,1,2,3,1,2,3$ 应保留后两段。
• 从原序列出现过的三音符段中选最优段：比只看第一段更强，但最优片段甚至可能没有完整出现过。例如 $1,2,4,1,4,3,4,2,3$ 中，三类众数为 $1,2,3$，只改三个位置即可；原来出现过的三段都至少要改四个位置。
• 要求三个音符互异：$2,2,1$ 本来就合法，不应修改。
• 全局只选一个众数：忽略了三种位置的分工，例如 $1,2,3,1,2,3$ 不需修改。

对每个候选音符都重新扫描整段序列的 $O(NK)$ 做法是正确慢解，在本场小规模档可得 30 分；若再结合固定目标性质可以取得 50 分。它不应被当成答案错误的程序。

赛时识别

先确认“同一段重复”而非“每一段各自合法”，再把相同段内位置列到一起，就能看见三组互不影响的选择。不需要贪心交换、动态规划或搜索整段改法。

T2 公告展示（display）

简要题意

每组给出发布时段长度 $K$ 和 $N$ 条按发布时间严格递增排列的公告，其中 $1\le N\le200000$、$N\le K\le10^9$。第 $i$ 条公告在整数时刻 $t_i$ 发布，仅在区间 $[t_i,t_i+d_i)$ 内有效，$0\le t_1<\cdots<t_N<K$，寿命 $d_i$ 取自 $\{0,120,300,600,1800,3600,7200,10800,14400,18000\}$。屏幕只展示当前有效公告中最新的三条；被遮挡不暂停寿命，旧公告可能重新出现。时刻 $K$ 后停止发布但不停止展示。按发布顺序逐行输出每条公告累计可见的秒数。输入至多 $10$ 组，同文件 $\sum N\le800000$。

一句话题解

将发布和到期时刻排序，用懒删除数组栈维护最新的三条有效公告，把相邻事件间的时间整段计入它们的答案。

完整题解

从文字提取模型

需要区分“有效”和“可见”：有效性只取决于 $t_i\le t<t_i+d_i$，可见性还要求当前较新的有效公告不超过两条。被挤出屏幕不会使公告失效，也不会改变它的到期时刻。

对 $d_i>0$ 的公告建立两个事件：在 $t_i$ 发布，在 $t_i+d_i$ 到期。$d_i=0$ 的公告答案为 $0$，不参与维护。公告只会在这些事件时刻改变状态，相邻事件之间展示内容保持不变，无须逐秒枚举。

用数组栈找最新的三条

发布时间严格递增，后发布的公告编号也更大。新公告发布时，将它压入栈。公告到期时，只标记该编号已经失效；即使它藏在栈内，也不用立即从中间删除。

需要确定当前展示者时，从栈顶依次取出编号：已失效的永久弹掉；仍有效的暂存，最多取三条。暂存的这些编号就是当前最新的三条有效公告。结算后，按与取出相反的顺序放回，以维持原栈顺序。不能丢掉它们下面仍有效的公告，因为它们以后可能重新显示。

按同一时刻批量处理

把全部事件按时间排序。设上次处理完的事件时刻为 $last$，当前事件时刻为 $now$：

1. 根据当前栈和失效标记确定展示者，为它们各增加 $now-last$。
2. 一起处理时刻 $now$ 的全部发布和到期事件。
3. 令 $last=now$。

第 1 步结算的是 $[last,now)$，第 2 步建立的是从 $now$ 开始的新状态。这样同刻发布和到期不需要人为规定谁先获得一秒时间，也不依赖排序对同刻事件的相对顺序。处理到最后一个到期事件即可，不能在 $K$ 停止。

正确性证明

首先，两相邻事件间没有公告发布或到期，有效集合不变，所以最新的三条有效公告也不变。为它们各增加整个区间长度，等价于逐秒统计。

其次，初始栈为空。新公告编号递增，压栈后顺序仍按发布时间排列；删除失效公告不会改变剩余编号的相对顺序；临时取出的有效公告反序放回，也不会改变原顺序。因此，从栈顶略过所有失效编号后，取出的前三条恰好是当前最新的三条有效公告。

算法在每个事件间隔都为且仅为实际展示者增加正确的时长，并覆盖所有有效时段，故所有输出正确。

复杂度与整数范围

每条公告只会首次入栈一次、因失效永久出栈至多一次。每批事件额外临时取出和还原至多三条，所以所有栈操作总计 $O(N)$；排序耗时 $O(N\log N)$，总空间 $O(N)$。

单条答案不超过 $18000$；所有事件时刻不超过 $10^9+18000$，因此本题参考实现使用 int 足够。多组测试之间要清空答案、失效标记以及事件和栈的长度。

部分分路线

分数	做法与适用范围
15	所有寿命均为 $120$ 时，先发布的先到期。第 $i$ 条至迟在第 $i+3$ 条发布时被遮挡，此后不会重新出现。答案为 $\min(120,t_{i+3}-t_i)$；不足三条后继时为 $120$。对应测试点 $1\sim3$。
35	将事件排序后，每个事件间隔扫描全部 $N$ 条公告，选出最新三条。时间 $O(N^2)$，对应测试点 $4\sim10$。
50	同寿命时使用上述公式，否则使用事件全扫描；两种真实方法组合，对应测试点 $1\sim10$。
75	按整数秒推进，用数组栈跳过过期公告、取出最新三条并还原。时间 $O(N+K+18000)$，对应测试点 $1\sim15$。
100	将逐秒推进改为事件推进，使用完整算法。

同寿命公式对于其他统一寿命也成立；有序集合维护有效编号同样是正确的满分实现。不能仅凭代码使用了 set 或 int 就判断做法错误。倒序扫描时找到三条就提前退出，或者逐秒模拟遇到空闲就跳跃，都不保证解决各自最坏情况。

还有一条自然的 50 分路线：倒序扫描只考虑已经发布的正寿命公告，并在超出本组最大寿命的时间窗口时停止。第一档的窗口只有 $120$ 秒，且发布时间是互异整数，因此每次至多检查 $120$ 条，能够兼得第一档与小规模两档。这不是完整算法：长寿命旧公告被大量较新短寿命公告遮挡后，较新公告即使已经过期，也可能仍处于 $18000$ 秒窗口内，被反复扫描；记录前缀最大到期时刻再提前停止，也不能消除这种情况。

15 分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, k, t[N], d[N], ed[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) {
			cin >> t[i] >> d[i];
			ed[i] = t[i] + d[i], ans[i] = 0;
		}
		for (int i = 1; i <= n; i ++)
			ans[i] = i + 3 <= n ? min(d[i], t[i + 3] - t[i]) : d[i];
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

35 分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int e[N * 2];
int n, k, t[N], d[N], ed[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) {
			cin >> t[i] >> d[i];
			ed[i] = t[i] + d[i], ans[i] = 0;
		}
		int m = 0;
		for (int i = 1; i <= n; i ++) {
			e[++ m] = t[i];
			e[++ m] = ed[i];
		}
		sort(e + 1, e + m + 1);
		for (int j = 1; j < m; j ++) {
			if (e[j] == e[j + 1]) continue;
			int cnt = 0;
			for (int i = n; i; i --) {
				if (t[i] <= e[j] && e[j] < ed[i]) {
					if (cnt < 3) ans[i] += e[j + 1] - e[j];
					cnt ++;
				}
			}
		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

50 分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int e[N * 2];
int n, k, t[N], d[N], ed[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) {
			cin >> t[i] >> d[i];
			ed[i] = t[i] + d[i], ans[i] = 0;
		}
		bool same = true;
		for (int i = 1; i <= n; i ++) if (d[i] != d[1]) same = false;
		if (same) {
		for (int i = 1; i <= n; i ++)
			ans[i] = i + 3 <= n ? min(d[i], t[i + 3] - t[i]) : d[i];
		} else {
		int m = 0;
		for (int i = 1; i <= n; i ++) {
			e[++ m] = t[i];
			e[++ m] = ed[i];
		}
		sort(e + 1, e + m + 1);
		for (int j = 1; j < m; j ++) {
			if (e[j] == e[j + 1]) continue;
			int cnt = 0;
			for (int i = n; i; i --) {
				if (t[i] <= e[j] && e[j] < ed[i]) {
					if (cnt < 3) ans[i] += e[j + 1] - e[j];
					cnt ++;
				}
			}
		}
		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

75 分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int st[N], tmp[3];
int n, k, t[N], d[N], ed[N], ans[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) {
			cin >> t[i] >> d[i];
			ed[i] = t[i] + d[i], ans[i] = 0;
		}
		int r = 0, top = 0, p = 1;
		for (int i = 1; i <= n; i ++) r = max(r, ed[i]);
		for (int now = 0; now < r; now ++) {
			while (p <= n && t[p] == now) {
				if (d[p]) st[++ top] = p;
				p ++;
			}
			int cnt = 0;
			while (top && cnt < 3) {
				int u = st[top --];
				if (ed[u] <= now) continue;
				ans[u] ++;
				tmp[cnt ++] = u;
			}
			while (cnt) st[++ top] = tmp[-- cnt];

		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

典型误读

考虑四条公告 $(t_i,d_i)$ 分别为 $(0,3600),(1,1800),(2,600),(3,600)$。第 $1$ 条在 $[0,3)$ 显示，在 $[3,602)$ 被遮挡，又在 $[602,3600)$ 显示，累计 $3+(3600-602)=3001$ 秒。把被遮挡公告永久删除，只能算出 $3$ 秒；把隐藏时间暂停，则会误认为它能显示满 $3600$ 秒。

“允许重新出现一次”也不足以修复错误：让一条长寿命公告之后，每隔一段时间发布三条短寿命公告，它会反复被遮挡、反复重新出现。只保留最近若干条也没有依据，较旧的长寿命公告可能在大量较新公告到期后才回到屏幕。

参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct Event {
	int t, id, op;
	bool operator < (const Event &b) const {
		return t < b.t;
	}
} e[N * 2];
int n, k, m, top, st[N], ans[N], tmp[3];
bool del[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> k;
		m = top = 0;
		for (int i = 1; i <= n; i ++) {
			int t, d;
			cin >> t >> d;
			ans[i] = 0, del[i] = false;
			if (!d) continue;
			e[++ m] = {t, i, 1};
			e[++ m] = {t + d, i, 0};
		}
		sort(e + 1, e + m + 1);
		int last = 0;
		for (int i = 1; i <= m;) {
			int now = e[i].t, cnt = 0;
			while (top && cnt < 3) {
				int u = st[top --];
				if (del[u]) continue;
				ans[u] += now - last;
				tmp[cnt ++] = u;
			}
			while (cnt) st[++ top] = tmp[-- cnt];
			while (i <= m && e[i].t == now) {
				if (e[i].op) st[++ top] = e[i].id;
				else del[e[i].id] = true;
				i ++;
			}
			last = now;
		}
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

T3 巡检路线（inspect）

简要题意

每组给出一棵 $N$ 个节点的无权树和 $M$ 个不同的必检节点，$2\le M\le N\le10^5$，节点编号为 $0\sim N-1$。任选起点和终点，沿边行走，每次经过一条边花费 $1$，允许重复经过节点、边；求至少访问一次全部必检节点的最少移动次数。输入至多 $10$ 组，同文件 $\sum N\le2\times10^5$，逐组输出一个整数。

一句话题解

剥去没有巡检任务的枝条，求剩余必要子树的边数 $E$ 和直径 $D$，答案为 $2E-D$。

完整题解

从巡检任务提取必要子树

道路连通且恰好有 $N-1$ 条，因此构成一棵树，两点间的简单路径唯一。

如果一个叶子不是必检点，进入这个叶子没有必要，可以删去它。删除后新出现的非必检叶子同样可以继续删除。用队列反复处理，留下的树记为 $H$。

不能只删除最初的非必检叶子：一条很长的无关枝条必须从外向内全部去掉。必检点即使成为叶子，也不能删除。

$H$ 恰好是连接全部必检点的最小子树：其中任意一条边的两侧都包含必检点，否则没有必检点的一侧还可以继续被剥掉。因此这些边都必须经过；被删掉的边则完全不需要经过。

为什么答案是两倍边数减直径

设 $H$ 有 $E$ 条边。先固定起点 $s$ 和终点 $t$。

将树中一条边删除，树会分成两个部分。若该边位于 $s$ 到 $t$ 的路径上，行程至少经过它一次；若不在这条路径上，为了访问另一侧的必检点，必须走过去再回来，至少经过两次。

因此，任意行程的代价至少为

$$2E-\operatorname{dist}(s,t).$$

这个下界能够达到：沿着 $s$ 到 $t$ 的路径前进，遇到侧枝时先往返完成侧枝的巡检，再继续沿主路径前进。主路径上的每条边恰好走一次，其余边恰好走两次。

起点和终点可以自由选择，所以应让两点距离最大，也就是取必要子树的直径 $D$。答案就是

$$\boxed{2E-D}.$$

不需要把起终点放在被删除的枝条里：删去到达第一个必检点前、离开最后一个必检点后的多余行走，不会让答案变差。

如何求直径

从 $H$ 中任意一个节点出发，找到距离最远的节点 $p$；再从 $p$ 出发，找到距离最远的节点 $q$。树上的最远点性质保证 $p$ 是某条直径的端点，第二次遍历得到的距离就是直径长度。

两遍均可使用 BFS。遍历时跳过已被剥离的节点，不要使用原树的直径代替必要子树的直径。

剥去一个叶子就减少一条边，因而从 $E=N-1$ 开始，每剥去一个节点执行一次 $E--$ 即可。

正确性小结

1. 非必检叶子及其逐步形成的无关枝条不必经过，剥离保留的每条边却必不可少。
2. 固定起终点后，主路径边至少一次、其他必要边至少两次，且存在达到该下界的行程。
3. 两端自由，使主路径最长便能使总路程最短；两次 BFS 求得最长主路径。

所以参考程序输出的 $2E-D$ 恰为最优答案。

复杂度与实现

每个节点至多入剥叶队列一次，每条边至多被检查常数次；两遍 BFS 同样为线性时间。总时间复杂度 $O(N)$，空间复杂度 $O(N)$。

答案不超过 $2(N-1)$，使用 int 足够。参考实现使用全局数组和 vector<int> e[N] 邻接表，整个过程不递归，能处理长链。多测时应重置邻接表、度数、必检标记和删除标记。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int n, m, a[N], deg[N], q[N], dist[N];
bool key[N], del[N];
int bfs(int s) {
	fill(dist, dist + n, -1);
	int hh = 0, tt = 0, p = s;
	q[tt ++] = s, dist[s] = 0;
	while (hh < tt) {
		int u = q[hh ++];
		if (dist[u] > dist[p]) p = u;
		for (int v : e[u]) {
			if (del[v] || dist[v] != -1) continue;
			dist[v] = dist[u] + 1;
			q[tt ++] = v;
		}
	}
	return p;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 0; i < n; i ++) {
			e[i].clear();
			deg[i] = 0, key[i] = del[i] = false;
		}
		for (int i = 0; i < m; i ++) {
			cin >> a[i];
			key[a[i]] = true;
		}
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
			deg[u] ++, deg[v] ++;
		}
		int hh = 0, tt = 0, cnt = n - 1;
		for (int i = 0; i < n; i ++)
			if (!key[i] && deg[i] == 1) q[tt ++] = i;
		while (hh < tt) {
			int u = q[hh ++];
			del[u] = true, cnt --;
			for (int v : e[u]) {
				if (del[v]) continue;
				deg[v] --;
				if (!key[v] && deg[v] == 1) q[tt ++] = v;
			}
		}
		int p = bfs(a[0]), t = bfs(p);
		cout << 2 * cnt - dist[t] << "\n";
	}
	return 0;
}

部分分：两个必检点，20 分

只有两个必检点时，沿两点间唯一路径走一遍即可，答案就是它们的距离。

下面的参考程序在原树中遍历，只在必检点里选择最远点：从一个必检点出发找最远必检点 $p$，再从 $p$ 找最远必检点 $q$，输出两者距离。$M=2$ 时恰好得到这两个点之间的距离，不需要先求必要子树；一般情况下只输出必检点间的最大距离，会漏掉侧枝的往返路程。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int n, m, a[N], q[N], dist[N];
bool key[N];
int bfs(int s) {
	fill(dist, dist + n, -1);
	int hh = 0, tt = 0, p = s;
	q[tt ++] = s, dist[s] = 0;
	while (hh < tt) {
		int u = q[hh ++];
		if (key[u] && dist[u] > dist[p]) p = u;
		for (int v : e[u]) {
			if (dist[v] != -1) continue;
			dist[v] = dist[u] + 1;
			q[tt ++] = v;
		}
	}
	return p;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 0; i < n; i ++) e[i].clear(), key[i] = false;
		for (int i = 0; i < m; i ++) {
			cin >> a[i];
			key[a[i]] = true;
		}
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
		}
		int p = bfs(a[0]), t = bfs(p);
		cout << dist[t] << "\n";
	}
	return 0;
}

部分分：枚举访问顺序，50 分

从某个必检点出发，将全部必检点排成一个顺序，依次沿最短路径走到下一个必检点。枚举所有排列，取路程最小值。

途中顺道经过其他必检点不影响合法性，也不需要禁止重复访问。任意排列给出一条合法行程；反过来，取最优行程首次访问必检点的顺序，将相邻两点之间的行走替换为最短路径，不会变差。因此枚举完整一定正确。

小档可以先对每个必检点 BFS，预处理点间距离，复杂度 $O(MN+M!\,M)$。$M\le8$ 时最多只有 $8!=40320$ 个排列。

下面的参考程序用 $O(N)$ 空间保存父亲和深度，在累加路径时逐层求距离。若树高为 $H$，实际复杂度为 $O(N+M!\,M H)$。本档 $N\le100,M\le8,H\le99$，能够完成枚举；一般档的排列数无法承受。

同一个枚举程序可以覆盖 $M=2$、$M\le3$ 和 $M\le8$ 的全部数据，共获得 $50$ 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
vector<int> e[N];
int n, m, a[N], deg[N], q[N], dist[N], fa[N], p[N];
bool key[N], del[N], used[N];
int get_dist(int u, int v) {
	int ans = 0;
	while (u != v) {
		if (dist[u] < dist[v]) swap(u, v);
		u = fa[u], ans ++;
	}
	return ans;
}
void prepare() {
	fill(dist, dist + n, -1);
	int hh = 0, tt = 0;
	q[tt ++] = 0, dist[0] = 0, fa[0] = 0;
	while (hh < tt) {
		int u = q[hh ++];
		for (int v : e[u]) {
			if (dist[v] != -1) continue;
			dist[v] = dist[u] + 1, fa[v] = u;
			q[tt ++] = v;
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 0; i < n; i ++) {
			e[i].clear();
			deg[i] = 0, key[i] = del[i] = false;
		}
		for (int i = 0; i < m; i ++) {
			cin >> a[i];
			key[a[i]] = true;
		}
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
			deg[u] ++, deg[v] ++;
		}
		prepare();
		sort(a, a + m);
		LL ans = 1e18;
		do {
			LL sum = 0;
			for (int i = 1; i < m; i ++) sum += get_dist(a[i - 1], a[i]);
			ans = min(ans, sum);
		} while (next_permutation(a, a + m));
		cout << ans << "\n";
	}
	return 0;
}

部分分：枚举起点，60 分

完成必要子树和 $2E-D$ 的推导后，如果还不会用两遍 BFS 求直径，可以从每个必检点出发各做一次 BFS，取这些遍历中出现的最大距离。

必要子树的所有叶子均为必检点，而直径端点一定可以取为叶子，因此只枚举必检点不会漏掉直径。复杂度 $O(MN)$，可完成 $N\le1000$ 的数据；一般档 $M,N$ 同时较大时不能承受。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> e[N];
int n, m, a[N], deg[N], q[N], dist[N];
bool key[N], del[N];
int bfs(int s) {
	fill(dist, dist + n, -1);
	int hh = 0, tt = 0, p = s;
	q[tt ++] = s, dist[s] = 0;
	while (hh < tt) {
		int u = q[hh ++];
		if (dist[u] > dist[p]) p = u;
		for (int v : e[u]) {
			if (del[v] || dist[v] != -1) continue;
			dist[v] = dist[u] + 1;
			q[tt ++] = v;
		}
	}
	return p;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 0; i < n; i ++) {
			e[i].clear();
			deg[i] = 0, key[i] = del[i] = false;
		}
		for (int i = 0; i < m; i ++) {
			cin >> a[i];
			key[a[i]] = true;
		}
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
			deg[u] ++, deg[v] ++;
		}
		int hh = 0, tt = 0, cnt = n - 1;
		for (int i = 0; i < n; i ++)
			if (!key[i] && deg[i] == 1) q[tt ++] = i;
		while (hh < tt) {
			int u = q[hh ++];
			del[u] = true, cnt --;
			for (int v : e[u]) {
				if (del[v]) continue;
				deg[v] --;
				if (!key[v] && deg[v] == 1) q[tt ++] = v;
			}
		}
		int diameter = 0;
		for (int i = 0; i < m; i ++) {
			int t = bfs(a[i]);
			diameter = max(diameter, dist[t]);
		}
		cout << 2 * cnt - diameter << "\n";
	}
	return 0;
}

常见错误与反例

• 只输出两个必检点之间的最远距离，会漏掉必要侧枝的往返。
• 直接计算原树的 $2(N-1)-D$，会被很长的无关枝条影响。
• 剥离无关枝条后仍减去原树直径，混用了两棵不同的树。
• 强制回到起点，得到 $2E$，没有利用终点自由。
• 固定第一个必检点为起点，可能放弃更长的主路径。
• 最近必检点优先没有全局最优性；多试若干起点或进行严格改善的区间反转，也不能代替证明。

例如，中心向三个必检叶子分出长度为 $1,2,4$ 的三条路径。必要子树有 $7$ 条边，直径为 $6$，答案是 $8$。若固定从最短分支的叶子出发，再贪心前往最近的另一片叶子，需要走 $3+6=9$。只输出最远距离会输出 $6$，强制返回则会输出 $14$。

赛时识别

先从“两个必检点”获得路径距离的入口；必检点很少时直接枚举访问排列，不必急着猜贪心。继续观察哪些枝条根本没有任务，再讨论必须往返的边。把起终点之间能省去一次往返的路径找出来，才会自然得到直径，而不是看到树就直接套原树直径。

T4 园区路网（network）

简要题意

每组给出 $N$ 个园区、每个园区内相同编号的 $M$ 座场馆，以及 $P$ 条内部道路记录、$Q$ 条园区间道路记录。内部记录在每个园区复制一次，园区间记录在每个场馆编号复制一次，实际有 $NM$ 个点、$NP+MQ$ 条无向边；允许重边、自环，原图保证连通。可以分别删除任意实际道路，求保持全连通时能节省的最大费用。$1\le N,M,P,Q\le10^5$，费用为 $1\sim10^8$，每文件至多 $10$ 组，四参数的文件内总和分别不超过 $2\times10^5$，逐组输出一个整数。

一句话题解

把所有基础边混合按维护费排序，用两个并查集维护两个维度，成功合并时乘上另一维当前连通块数，得到实际路网的最小生成树费用，再从原总费用中扣除。

完整题解

1. 先看清实际道路，再反过来计算保留费用

同一记录的副本可以分别关闭，不是要么全部保留、要么全部删除。每条内部记录出现 $N$ 次，每条园区间记录出现 $M$ 次，因此原费用为

$$S=N\sum_{i=1}^{P}c_i+M\sum_{j=1}^{Q}z_j$$

最大节省等价于最小保留。费用均为正，保留的连通图中如果存在环，就可以删去环上一条边并进一步节省。因此最优保留方案可以是一棵最小生成树，答案为 $S-\operatorname{MST}$。

2. 15 分：所有费用都是 1

实际图有 $NM$ 个点，连通树一定有 $NM-1$ 条边。所有边费用都是 1，所以最小保留费用直接是 $NM-1$，答案为

$$NP+MQ-NM+1$$

读完所有输入记录即可，时间 $O(P+Q)$、额外空间 $O(1)$。这条公式在其他规模的单位费用输入上也成立；本题专门保证这项性质的范围是测试点 1～3。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		LL n, m, p, q;
		cin >> n >> m >> p >> q;
		for (int i = 1; i <= p + q; i ++) {
			int a, b, w;
			cin >> a >> b >> w;
		}
		cout << n * p + m * q - n * m + 1 << "\n";
	}
	return 0;
}

3. 30 分：按题面完整展开小图

给实际点 $(x,a)$ 编号 $(x-1)M+a$，将所有副本道路加入边数组，直接排序并运行普通 Kruskal。

不能只看到 $P,Q\le200$ 就担心 $NM$ 仍然很大：原图连通保证两个维度的投影图各自连通，因此 $M-1\le P$、$N-1\le Q$。这一档最多 $201^2=40401$ 个实际点、$2\times201\times200=80400$ 条实际边。重边、自环只会浪费记录，不能破坏这个上界。

设 $V=NM,E=NP+MQ$，完整展开的时间为 $O(E\log E+E\alpha(V))$，空间为 $O(V+E)$。下面代码的数组容量支持这一公开档位。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 40500, M = 1e6 + 10;
struct Edge {
	int a, b, w;
	bool operator < (const Edge &t) const { return w < t.w; }
} e[M];
int n, m, p, q, cnt, fa[N], sz[N];
int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m >> p >> q;
		cnt = 0;
		LL ans = 0;
		for (int i = 1; i <= p; i ++) {
			int a, b, w;
			cin >> a >> b >> w;
			for (int j = 0; j < n; j ++) {
				e[++ cnt] = {j * m + a, j * m + b, w};
				ans += w;
			}
		}
		for (int i = 1; i <= q; i ++) {
			int a, b, w;
			cin >> a >> b >> w;
			for (int j = 1; j <= m; j ++) {
				e[++ cnt] = {(a - 1) * m + j, (b - 1) * m + j, w};
				ans += w;
			}
		}
		for (LL i = 1; i <= (LL)n * m; i ++) fa[i] = i, sz[i] = 1;
		sort(e + 1, e + cnt + 1);
		for (int i = 1; i <= cnt; i ++) {
			int a = find(e[i].a), b = find(e[i].b);
			if (a == b) continue;
			if (sz[a] < sz[b]) swap(a, b);
			fa[b] = a, sz[a] += sz[b], ans -= e[i].w;
		}
		cout << ans << "\n";
	}
	return 0;
}

4. 60 分：不存副本，只按顺序逐条处理

普通 Kruskal 只要求按权重非降序处理边。同一基础记录的副本权重完全相同，因此可以先只排序 $P+Q$ 条基础记录，再依次展开当前记录的所有副本，立即对实际点做并查集合并，不必把所有副本同时存入内存。

这种实现没有用到满分解的连通块压缩性质，仍在真实处理每条副本。时间为

$$O((P+Q)\log(P+Q)+(NP+MQ)\alpha(NM))$$

空间为 $O(P+Q+NM)$。在 $N,M\le200$ 的范围内，每组最多 4000 万次合并尝试；结合文件总量，所有组累计不超过 8000 万次。

这是建议讲给学生的 60 分路线：先由题面建出正确图，再避免把所有边同时存储。前一档可能达到 $201\times201$，数组至少按 40401 个点分配。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, M = 40500;
struct Edge {
	int a, b, w, op;
	bool operator < (const Edge &t) const { return w < t.w; }
} e[N];
int n, m, p, q, fa[M], sz[M];
int find(int x) {
	while (x != fa[x]) x = fa[x] = fa[fa[x]];
	return x;
}
bool merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return false;
	if (sz[a] < sz[b]) swap(a, b);
	fa[b] = a, sz[a] += sz[b];
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m >> p >> q;
		LL ans = 0;
		for (int i = 1; i <= p + q; i ++) {
			cin >> e[i].a >> e[i].b >> e[i].w;
			e[i].op = i > p;
			ans += (LL)e[i].w * (i <= p ? n : m);
		}
		for (LL i = 1; i <= (LL)n * m; i ++) fa[i] = i, sz[i] = 1;
		sort(e + 1, e + p + q + 1);
		for (int i = 1; i <= p + q; i ++) {
			if (!e[i].op) {
				for (int j = 0; j < n; j ++)
					if (merge(j * m + e[i].a, j * m + e[i].b)) ans -= e[i].w;
			} else {
				for (int j = 1; j <= m; j ++)
					if (merge((e[i].a - 1) * m + j, (e[i].b - 1) * m + j)) ans -= e[i].w;
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

5. 另一条 60 分路线：先在两个维度各留一棵 MST

分别对场馆编号图和园区图求一棵 MST，仅保留被选中的基础记录，再展开求实际图的 MST。

对一条没有选入本维 MST 的边，本维 MST 中连接其端点的路径上，每条边的权重都不大于它。将这条路径复制到任一层，仍可替代被删边。换言之，删去这些基础记录后，各权值阈值下的连通关系不变，实际图的 MST 权重也不变。

两个维度分别只剩 $M-1$、$N-1$ 条基础边，第三档展开后至多 $N(M-1)+M(N-1)\le79600$ 条实际边。复杂度为 $O((P+Q)\log(P+Q)+NM\log(NM))$，空间为 $O(N+M+P+Q+NM)$。它也是合法 60 分路线，但学生不必想到这个额外性质才能争取 60 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 80500;
struct Edge {
	int a, b, w, op;
	bool operator < (const Edge &t) const { return w < t.w; }
} e[N * 2], g[M];
int n, m, p, q, cnt, fa[N * 2], sz[N * 2];
int find(int x) {
	if (fa[x] != x) fa[x] = find(fa[x]);
	return fa[x];
}
bool merge(int a, int b) {
	a = find(a), b = find(b);
	if (a == b) return false;
	if (sz[a] < sz[b]) swap(a, b);
	fa[b] = a, sz[a] += sz[b];
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m >> p >> q;
		LL ans = 0;
		cnt = 0;
		for (int i = 1; i <= n + m; i ++) fa[i] = i, sz[i] = 1;
		for (int i = 1; i <= p + q; i ++) {
			cin >> e[i].a >> e[i].b >> e[i].w;
			e[i].op = i > p;
			ans += (LL)e[i].w * (i <= p ? n : m);
		}
		sort(e + 1, e + p + q + 1);
		for (int i = 1; i <= p + q; i ++) {
			int a = e[i].a, b = e[i].b, w = e[i].w;
			if (!e[i].op) {
				if (!merge(a, b)) continue;
				for (int j = 0; j < n; j ++) g[++ cnt] = {j * m + a, j * m + b, w, 0};
			} else {
				if (!merge(a + m, b + m)) continue;
				for (int j = 1; j <= m; j ++) g[++ cnt] = {(a - 1) * m + j, (b - 1) * m + j, w, 0};
			}
		}
		for (LL i = 1; i <= (LL)n * m; i ++) fa[i] = i, sz[i] = 1;
		sort(g + 1, g + cnt + 1);
		for (int i = 1; i <= cnt; i ++)
			if (merge(g[i].a, g[i].b)) ans -= g[i].w;
		cout << ans << "\n";
	}
	return 0;
}

6. 满分：批量完成重复的合并

不再为每个实际点维护并查集，而是只维护园区编号与场馆编号两个维度的并查集。

设当前园区连通块数为 $n_c$，场馆编号连通块数为 $m_c$，初始分别为 $N,M$。将两类基础边一起按费用排序。

• 内部道路连接两个不同场馆块时，保留费用增加 $c_i n_c$，合并这两个场馆块，令 $m_c$ 减 1。
• 园区间道路连接两个不同园区块时，保留费用增加 $z_j m_c$，合并这两个园区块，令 $n_c$ 减 1。
• 对应维度已经连通，则所有副本都无需再选。

同权记录可任意排序，关键是每条处理后立即更新连通块数。

7. 正确性证明

维护不变量：完整处理每条基础记录的所有副本后，实际图的每个连通块都形如“一个园区块 $X$ 与一个场馆编号块 $A$ 的笛卡尔积 $X\times A$”。初始每个块仅一个实际点，不变量成立。

考虑一条内部道路，其两个场馆编号分别在不同块 $A,B$ 中。对每个园区块 $X$，这条记录的一批副本会连接 $X\times A$ 和 $X\times B$。为了连接这两个块，只需要保留一条副本，其他副本均会成环。共有 $n_c$ 个园区块，所以恰好保留 $n_c$ 条该费用的边。处理后形成 $X\times(A\cup B)$，不变量继续成立。园区间道路同理。

若端点本就在同一维度块中，所有副本端点都已连通，应全部跳过。由此每一步都是实际展开图上合法的一批 Kruskal 操作；基础边按非降权重处理，所以最终得到实际图的 MST。原费用扣去该值即为最大节省。

8. 复杂度与实现边界

时间为 $O((P+Q)\log(P+Q)+(P+Q)\alpha(N+M))$，空间为 $O(N+M+P+Q)$。并查集采用按大小合并与路径压缩。

原总费用最多 $2\times10^{18}$，必须先转成 long long 再乘；实际点数 $NM$ 本身也可能超过 32 位。满分程序不计算实际点编号，不需要创建 $NM$ 大小的数组。

每组都重新初始化两个并查集、块数与答案；自环由端点已连通自动跳过；重边需保留在原费用中，即使它最终不进入 MST。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct Edge {
	int a, b, w, op;
	bool operator < (const Edge &t) const {
		return w < t.w;
	}
} e[N * 2];
int n, m, p, q, fa[2][N], sz[2][N], cnt[2];
int find(int op, int x) {
	if (fa[op][x] != x) fa[op][x] = find(op, fa[op][x]);
	return fa[op][x];
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m >> p >> q;
		cnt[0] = m, cnt[1] = n;
		for (int op = 0; op < 2; op ++)
			for (int i = 1; i <= cnt[op]; i ++) fa[op][i] = i, sz[op][i] = 1;
		LL ans = 0;
		for (int i = 1; i <= p + q; i ++) {
			cin >> e[i].a >> e[i].b >> e[i].w;
			e[i].op = i > p;
			ans += (LL)e[i].w * (i <= p ? n : m);
		}
		sort(e + 1, e + p + q + 1);
		for (int i = 1; i <= p + q; i ++) {
			int op = e[i].op, a = find(op, e[i].a), b = find(op, e[i].b);
			if (a == b) continue;
			ans -= (LL)e[i].w * cnt[op ^ 1];
			if (sz[op][a] < sz[op][b]) swap(a, b);
			fa[op][b] = a, sz[op][a] += sz[op][b];
			cnt[op] --;
		}
		cout << ans << "\n";
	}
	return 0;
}

9. 容易误判的方向

固定乘最初的 $N,M$。 前面的道路已把另一维部分连通，后面的记录可能不再需要保留所有副本，乘数必须随合并改变。

先连完一个维度，再处理另一个维度。 两类边的价格可能交错，即使把两种先后顺序都算一遍再取优，仍不一定正确。例如 $N=M=3$，内部边为 $(1,2,1),(2,3,100)$，园区间边为 $(1,2,2),(2,3,99)$。原费用为 606，正确保留费用为 $3+4+198+100=305$，节省 301；先完整连接任一维度，都只能节省 202。

同权批量时使用处理前的块数计算全部贡献。 同权不要求优先处理某一维度，但合并后的块数必须影响后续记录。可以任意次序执行正确的逐条合并，不能让同权的两维贡献都使用旧块数。

输出保留费用。 题目要的是节省的费用，还需从原总费用中扣除。