1. 从零开始读懂这道题Remove the Grail Tree 到底在问什么先说结论这道 CF2193H 的题目名字取得很唬人但把表面的“圣杯”“树形”滤镜摘掉之后它本质上是一个非常经典的树上配对问题甚至可以说它考察的就是树的最大匹配。只要你能看穿这一层剩下的贪心过程就是半小时内能写出来的事。题目描述非常短。给定一棵无根树你每次可以选择一条仍然存在的边然后把这条边的两个端点以及它们关联的所有边直接移除。移除之后树会被切成若干连通块这些连通块继续作为独立的树处理。最后如果只剩下孤立点也可以直接把它删掉。问把整棵树删干净最少需要多少次操作我第一次看到这个题的时候第一反应是“这不就是个模拟删边题吗”。但如果你真去模拟每一步删哪条边就会很快发现事情不对这不是一个让你挑选删除顺序的模拟题而是一个让你算全局最优值的组合优化题。因为它每一步删除两个相邻点所以答案天然和“配对”有关。换句话说你每次操作实际上就是在树的一堆点里面挑一对相邻的点“消灭”掉。既然如此问题就顺理成章地转化成了树上最多能凑出多少对相邻点。这篇题解报告我会从问题转化讲起把为什么答案是“点数减最大匹配数”讲透再给出一个基于 DFS 的树上贪心求最大匹配的完整做法和 AC 代码。题目本身难度不算太高但它背后的模型非常典型值得你把它当作一类“树上配对”题目的母题来研究。1.1 操作规则的本质每次操作就是一次配对先把这个模型彻底说清楚。树的节点数为 n。一次操作如果选择了一条边 (u, v)那么 u 和 v 都会被移除相当于把这两个点配成了一对。这个配对有一个硬条件u 和 v 之间必须存在一条边。所以你不能随便抓两个点删掉配对的点必须相邻。再看孤立点的删除。题目里如果树只剩一个点它没有相邻点但显然你仍然需要一次操作把它删掉。这就需要把规则补充完整允许用一次操作删除一个孤立点。这样一来整个删除过程就变成了两件事的组合若干次“配对删除”每次删除两个相邻点贡献 1 次操作若干次“单点删除”每次删除一个孤立点贡献 1 次操作。设我们用 M 次配对删除、S 次单点删除那么有 2M S n。总操作次数是 M S。把它整理成只依赖 M 的形式T M S M (n - 2M) n - M所以要让总操作次数 T 尽量小唯一要做的就是让 M 尽量大。也就是要最大化能配对的点对数。这不就是最大匹配吗配对的两个点之间必须有边而且每个点最多参与一次配对这就是标准意义上的匹配。1.2 一类常见误区为什么不是每次删除尽量大的连通块很多人看完题目之后会想到另一个方向既然每次删边会把树切成两个连通块那我如果每次选择一条靠近中间的边是不是能“顺带”把大片区域一起删掉这是对题意的误读。题目说的是删除边的两个端点而不是删除整条边两侧的子树。操作之后剩下的点依然保留它们会重新组成若干棵树。所以这道题和“树分块”“树的重心”这些都没有关系千万不要往那个方向想。如果你把题意读成“删除一条边以及该边两侧的所有节点”那答案自然变成了 1——选任意一条边整棵树就全没了题目没有任何考察价值。能出成 H 题说明它一定不是那种一锤子买卖。正确理解操作之后你会发现这个题反而像是在考察图论基础里的匹配概念而且由于是树最大匹配的求法可以比一般图简单得多。这就引出了下面要讲的贪心解法。2. 关键观察树上最大匹配为什么能用贪心求出来如果这是一张普通图求最大匹配就得用带花树这类重型算法。但这是树树上有非常好的结构可以直接贪心。2.1 从叶子开始往上配对贪心策略的直觉来源先想一想树上一片叶子能跟谁配对。一片叶子只有一个邻居也就是它的父亲。如果叶子暂时没有被匹配那么它最终要么不参与配对要么只能和父亲配对。如果最优解里叶子没有和父亲配对而这个叶子也没参与任何配对那我们完全可以把最优解中父亲和它原来的匹配对象拆开改成让叶子和父亲配对。这样做不会减少匹配边的数量因为原来的父亲匹配对象提供了 1 条匹配边新的叶子父亲组合同样提供了 1 条匹配边。这个交换论证告诉我们当叶子存在时总会存在一个最大匹配让这个叶子和它的父亲配对。也就是说对于当前树的叶子节点直接匹配它和它的父亲是“无损”的永远不会把答案做小。那么匹配掉一个叶子和它的父亲之后呢这两个点被删掉与它们相连的边也都被删除剩下的部分仍然是若干棵树。于是我们可以对剩下的树继续做同样的事情继续找叶子继续让叶子和父亲配对。这就是一个非常自然的递归贪心过程。实现的时候不需要真的去拆树只需要从下往上 DFS在后序位置检查当前节点的儿子是否还没有被匹配如果有未匹配的儿子就把自己和这个儿子配对。2.2 反证法证明贪心的最优性为了避免“感觉上对但实际写出来被卡”的尴尬这里还是把证明完整写一遍。设贪心算法得到匹配 G我们证明它的大小等于最大匹配。取树上的任意一片叶子 v设它的父亲为 u。如果存在一个不含边 (u, v) 的最大匹配 M若 v 未被匹配那么 u 一定被匹配到了某个点 w。我们把 u-w 这条匹配边替换成 u-v匹配数量不变仍然是最优的而且现在的匹配包含了 (u, v)。若 v 已经被匹配那唯一的可能就是 v 匹配了 u矛盾所以这种情况不存在。因此总能找到一个最大匹配包含边 (u, v)。既然如此贪心选择 (u, v) 不会妨碍我们达到最优。删掉这两个点之后剩余问题仍然是原问题的一个子问题继续套用相同论证归纳可得贪心匹配的大小就是最大匹配大小。这个证明简洁且无懈可击。我建议你把这套“交换论证”记下来因为在树上做贪心的题目里这种证明套路出现频率极高。2.3 一条重要的失败思路从根往下配对刚拿到题的时候我第一版代码是从根开始往下 DFS遇到一个节点就尽量和它某个儿子配对。这个方向是错误的。原因是如果从上往下配根节点可能会抢走某个子树里非常重要的一条匹配边导致下面的子树内部无法形成最优匹配。举一个极端例子一个根节点连着一条长度很长的链。从根往下贪心根先和链上的第二个节点配对剩下的链长度如果是偶数倒是还好但如果剩下的链长度是奇数最后会多出一个孤立点白白浪费一次配对机会。而从叶子往上的贪心会先把链尾部的相邻点全部配对配对数量永远是最足的。结论只有一句话树上匹配的贪心必须从叶子开始往上做。这也是我写所有树上动态规划的一个默认习惯能自底向上解决的问题尽量不自上而下。3. 算法细节与完整实现把贪心写成能 AC 的代码现在到了真正动手的环节。这里我给出一个 C17 的实现。整体思路是维护一个 matched 数组用 DFS 从下往上处理每个节点。3.1 数据结构与核心逻辑设计我使用 vector 存邻接表。注意 n 最大到 2e5如果用二维数组肯定不行必须用邻接表。递归 DFS 在这个规模下在 Codeforces 上一般没问题但为了保险有的选手会手写栈或者用迭代版本。实际测试下来2e5 的递归深度在大部分 OJ 上只要把栈空间开大一点或者用静态数组建图问题不大。后面我会给出一个相对稳的写法。核心逻辑只有几行从任意节点作为根开始 DFS。遍历每个儿子先递归处理儿子。从儿子返回之后检查儿子是否已经匹配以及当前节点是否已经匹配。如果两边都没匹配就把当前节点和儿子匹配匹配数加一。对于整棵树的根节点处理完所有儿子之后如果根节点没有被匹配它最终会变成孤立点单点删除也需要一次操作。不过我们最后的公式是 n - 最大匹配数这个公式已经天然把这个孤立点算进去了所以不需要单独处理。这里有一个细节值得单独提醒DFS 时一定要记录父节点避免在无向图里把父节点当成儿子往回走。否则你会匹配出一对“父子相认”但其实是同一条边的奇怪东西甚至无限递归。3.2 参考代码C17 完整题解#include bits/stdc.h using namespace std; vectorvectorint g; vectorint match; int ans 0; void dfs(int u, int p) { for (int v : g[u]) { if (v p) continue; dfs(v, u); if (!match[v] !match[u]) { match[u] match[v] 1; ans; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; g.assign(n 1, {}); match.assign(n 1, 0); for (int i 0; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); cout n - ans \n; return 0; }等一下可能有同学会问ans 不就是最大匹配数吗为什么答案要写成 n - ans结合第一部分的公式总操作次数 配对次数 孤立点点数 ans (n - 2 * ans) n - ans。没错一行代码的事但背后是整个模型。多测的时候记得把全局变量清干净。Codeforces 很多题都带 T 组数据如果全局 vector 不清空第二轮就会 RE 或者结果错乱。上面的代码是单组输入的写法你要是改成多测把 g、match、ans 都放进循环体里重新初始化即可。3.3 复杂度分析与空间考虑每个节点在 DFS 中恰好访问一次每条边也恰好遍历一次因此时间复杂度和空间复杂度都是 O(n)。对于 n2e5 的数据规模这个复杂度是非常舒服的运行时间通常不到 0.5 秒。空间上的一个隐患是递归深度。当树退化成一条链时递归深度达到 n。C 默认的栈空间在某些环境下可能不够用。我的写法里用的是 vector 邻接表每个节点的结构体重所以内存占用稍高但 2e5 是毫无压力的。如果实在担心递归爆栈可以用两个写法处理在 main 函数开头加一句扩展栈的命令。在 G 中你可以使用#pragma comment(linker, /STACK:1024000000,1024000000)但这在 Linux 上不一定有效。更通用的做法是写成迭代 DFS自己维护栈顺序先求出每个节点的父节点关系再按照逆后序遍历一遍。我个人在实际比赛中大多数情况直接写递归因为 CF 的栈空间给得比较充裕。你在本地测试极端的链型数据时如果出现栈溢出不要慌用迭代版即可。4. 从公式到直觉为什么答案就是 n 减最大匹配数到这里算法已经完全讲完了。但我觉得还需要把“n - 最大匹配数”这个式子彻底聊透不然很多读者看完代码之后会觉得自己只是背了一个公式遇到稍微变形的题目还是不会。4.1 用最小边覆盖的视角重新看问题在无孤立点的图中有一个经典结论最小边覆盖大小等于顶点数减去最大匹配大小。你现在回头看看我们这个问题每次操作删除一条边的两个端点本质上是选择一条边去覆盖它的两个端点。最终所有点都必须被“覆盖”到有些点通过配对删除被覆盖有些点通过单点删除被覆盖。换句话说我们希望用尽可能少的“边”去覆盖所有点。但要注意这里不能随便选边因为一条边只能覆盖两个端点而且不同边之间不能共用顶点。这正是最小边覆盖问题的定义。树作为图的一种这个结论同样成立。所以这道题其实就是披着“删除操作”外衣的最小边覆盖问题。4.2 三种常见树的答案验证只看公式不验证总让人心里不踏实我拿三种典型结构手算一下。一条链点数 n。最大匹配数是 floor(n/2)因此答案是 n - floor(n/2) ceil(n/2)。以 n5 为例1-2-3-4-5我们可以先删 (4,5)再删 (2,3)最后删孤立点 1三次操作答案 3 对。星形树一个中心点连接 n-1 个叶子。最大匹配数是 1最优匹配是中心点和某一个叶子配对。答案就是 n-1。实际操作确实如此第一次操作删中心点和叶子剩下的 n-2 个叶子全是孤立点每个都要单独删一次总共 1 (n-2) n-1。两两配对完成的完美匹配树比如一条链 n6。最大匹配数是 3答案也是 3。我们只需要连续选择不相邻的三条边比如 (1,2)、(3,4)、(5,6)三次操作全部删完。这几个例子都可以直接验证公式也能帮助你快速判断自己代码算出来的答案是否合理。4.3 操作顺序会不会影响答案在实际模拟中你可能发现操作顺序对最终答案确实没有影响。这是因为操作过程本质上就是把匹配边记录下来匹配边集合一旦确定操作总数就确定了。无论先删哪条匹配边剩下的结构都会自动保持“配对关系”不变。我们并不需要真的输出删除方案只需要计算数量。如果题目改成要输出具体删除顺序那就要注意了删掉一条匹配边后被删的两个点会连带删除与它们相邻的所有边如果其他匹配边和这两个点相邻就会出现冲突。好在我们求的匹配边两两不会共用端点所以它们之间不会直接相邻。这一点也再次说明了匹配概念在这里有多关键。5. 常见 Bug 与调试技巧这题的坑比想象中多每次写题解我都想重点写写踩坑记录因为这部分的经验往往是文档里不会告诉你的。这题代码量不大但一些小地方一不留神就写错而且错得还很隐蔽。5.1 最容易出的问题把匹配数组初始化位置搞错我见过很多同学写成这样for (int i 1; i n; i) { dfs(i, 0); }这样会把每个点都当成一棵新树的根去跑一遍。树是无向连通图根本不需要对每个点跑一次只需要从 1 号点开始 DFS 一次。如果你对每个点都跑一次同一个儿子可能会分别被自己和它的父节点尝试匹配导致匹配逻辑完全混乱答案会偏大。正确写法只调用一次dfs(1, 0)。5.2 注意无向图的父子关系dfs(v, u)这种写法在树上是安全的但如果你把dfs(v, u)写成了dfs(v, -1)或者在循环时没有跳过父节点就会发生严重的死循环。n2e5 时死循环并不是你肉眼能立刻看出来的只会表现为程序超时。建议在写任何无向图 DFS 时都务必要把父节点参数传下去。有一种更省心的写法是在 DFS 开始时用if (fa[u]) continue;之类的标记避免重复访问。但在树上传父节点参数是最自然的。5.3 最大匹配数到底能不能直接当成答案很多人写完贪心输出ans然后发现样例突然过不了或者答案比标准答案小很多。原因在于题目问的是“最少操作次数”实际上需要的是 n - ans。这个换算关系务必记牢。如果你只输出了匹配数你会把答案算小因为所有未被匹配的点你都漏掉了删除操作。5.4 验证用的暴力代码思路如果你想要更安心可以写一个针对小数据的暴力验证程序。枚举所有可能的操作序列取操作次数最小值然后和上面的贪心结果比对。具体暴力方法是用 DFS 枚举当前要删除的边或者用位运算状态压缩枚举匹配边集合。我建议至少对 n ≤ 10 的所有随机树跑一遍比对保证算法万无一失。这个习惯能帮你省下大量提交 WA 之后再怀疑人生的时间。下面给一个简单的随机树生成逻辑适合做对拍mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); for (int i 2; i n; i) { int p rng() % (i - 1) 1; cout i p \n; }每次生成的是一棵随机有根树对于无向图算法来说任何根化都等价可以直接用。6. 拓展思考这个模型还能解决什么问题一道好题的价值不在于本身而在于它能不能成为你解决一类问题的钥匙。“删除相邻点求最少次数”这个模型其实在很多题目里都会改头换面出现。6.1 变体一每次必须删除距离至少为 2 的两个点如果把规则改成只能删除不相邻的两个点那就不是匹配问题了而是变成了最大独立集问题。树上最大独立集可以用树形 DP 求解和这里的贪心完全不是一回事。如果你在赛场上看到这种变形要能立刻反应过来。6.2 变体二每次操作限定为删除一个点及其所有邻居这等价于在树上选尽量少的点使得每个点要么被选要么有邻居被选也就是树上的最小支配集问题。最小支配集在树上可以用贪心或树形 DP 求但复杂度更高状态更复杂。它和本题的思路有相通之处都是从叶子向根处理但状态转移完全不同。6.3 变体三树变成基环树如果图稍微复杂一点出现了一个环简单贪心是否仍然正确答案是不一定。环上会发生冲突可能需要对环进行额外的枚举或 DP。CF 上有不少题就是从树扩展到基环树的看到这种题目时你要习惯先判断是不是继承了树的贪心性质再决定是否要环上处理。所以我建议你把这道题整理进自己的“树上配对”笔记并把配套的最大匹配贪心证明也写进去。下一次遇到类似操作优先级最高的第一步永远是把操作翻译成图论概念而不是直接上模拟。7. 个人实战经验这道题给我留下的三个习惯最后聊一点个人体会。这道题虽然不是我这个赛季做过最难的题但它在训练里给了我三个比较重要的提醒。第一个习惯遇到“删除相邻点”的题目我第一反应会去看匹配相关性质。因为一次操作删除两个相邻点操作次数天然和点数的配对率挂钩。匹配、独立集、支配集这些概念在树上都有很成熟的结论先往这些方向靠往往能快速打开思路。第二个习惯树上的贪心证明不能省。许多人写这道题的时候会说“从叶子往上配对显然是正确的”然后不写证明直接交。确实大部分情况下能过但一旦遇到特殊构造的数据心里没底就会非常慌。我在训练时强制自己把交换论证写出来哪怕只是草稿也能加深理解。第三个习惯对拍是最后的保险。比赛时间紧张时很多选手不愿意写对拍。但这一题逻辑简单写一个暴力对拍只花几分钟却能让你在提交前确认所有边界情况。对我个人来说这种“慢一步”的稳妥反而让我的通过率更高。这道题就聊到这里。如果你对树形 DP 或者匹配相关的题目有兴趣可以把本题的贪心思路和最小边覆盖结论作为基础再去挑战环形图上的变式会顺畅很多。
