如果你在准备 USACO Silver 组2019 年 12 月的这道 Milk Visits 是绕不开的经典题。名字很温馨农场、奶牛、牛奶骨子里却是一道标准的树上路径查询问题给你一棵 N 个节点的树每个节点标记成 G 或 H再给你 M 次询问每次问从节点 a 到节点 b 的简单路径上存不存在标记为 c 的节点。N 和 M 都到 1e5指望每个询问都去 DFS 一遍路径基本是送死。这道题非常适合刚学完并查集、想往树论方向进阶的选手它没有复杂的模板堆砌却能让人真正理解存在性查询和连通性之间的等价关系。这篇文章会把题意、两种主流解法、正确性证明和调试经验一次讲透。1. 题目读法和题意还原1.1 输入输出到底长什么样题目给的信息很简洁。第一行两个整数 N 和 MN 是农场数量M 是询问次数。第二行是一个长度为 N 的字符串第 i 个字符表示第 i 个农场的牛奶类型只有 G 和 H 两种。接下来 N-1 行是农场的道路构成一棵无向树。最后 M 行是询问每行三个部分起点 a、终点 b、期望的牛奶类型 c。输出更是简洁到容易翻车一行长度为 M 的字符串第 i 个字符是 1 或 0表示第 i 次询问是否满足条件。举个例子我构造一个小数据5 5 HHGGG 1 2 1 3 2 4 2 5 1 2 G 1 3 H 4 5 H 3 4 G 2 4 H对应的输出是01111这里的含义是1 到 2 路径上都是 H没有 G所以第一问输出 01 到 3 路径上有 H输出 14 到 5 的路径要经过 2颜色是 G-H-G有 H输出 1其余同理。注意一个关键点这是一棵树所以任意两个农场之间恰好只有一条简单路径不存在最短路径选哪条的问题。这个性质是所有解法的基础。1.2 关键词路径、颜色、存在性拆开看这道题其实只有三个关键词路径、颜色、存在性。路径好理解树上的路径就是沿着边从一端走到另一端颜色是每个节点的属性G/H 二选一存在性则是问这条路径上有没有至少一个目标颜色节点。这三个词凑在一起很容易把思路带偏。很多第一次做这题的选手会想那我是不是要把路径上所有节点的颜色都收集一遍于是很自然地写出暴力 DFS出题人心里其实乐开了花——N 和 M 都到 1e5最坏情况是 1e5 次询问每次遍历 1e5 个点稳稳的超时。还有一部分选手会想既然颜色只有两种那我维护一个前缀和数组不就行了这个方向已经接近正解但银组阶段很多人还没系统学过 LCA于是又卡住了。实际上这道题 Silver 组的官方预期解法非常轻盈它不依赖 LCA只需要并查集和一次反向思维。这也是我特别想写这篇文章的原因有时候把问题反过来问答案会简单到让人惊讶。1.3 这道题适合什么人练如果你是刚学完图论基础、正准备冲刺 Silver 的选手这道题是绝佳的思维训练素材。它不会刁难你的代码能力却非常考验你能否跳出路径必须一步一步走的惯性。如果你已经在刷 Gold 组这道题同样有参考价值因为 LCA 加树上前缀计数的解法可以无缝迁移到更复杂的路径统计问题。文章后半部分会详细讲 LCA 路线把它当作一个买一送一的福利。2. 一个会改变解题方向的问题2.1 先从暴力开始写暴力解法不丢人重要的是从暴力里提炼出瓶颈。最直观的暴力是对每次询问 (a, b, c)从 a 出发 DFS/BFS 到 b沿途检查每个节点的颜色是否为 c。遇到目标颜色就返回 true走完一整条路径还没有就是 false。代码写起来不超过二十行跑起来却极其感人。复杂度是 O(NM)。当 NM1e5 时这是 1e10 级别的操作。哪怕评测机一秒能跑 1e8 次也要一百秒完全不可接受。那问题出在哪出在存在性三个字上。你要的是这条路径上是否至少有一个 c 色节点但你被迫把整条路径都走了一遍。有没有办法不去遍历完整条路径也能判断出是否有呢2.2 反过来问什么时候路径上会完全没有目标颜色大部分人的第一反应是研究路径上有什么但数学和算法里一个常用的技巧是研究它的对立面。既然存在难判断那就先判断不存在。路径上不存在颜色 c 的节点等价于什么等价于从 a 出发到 b中间不能碰到任何一个 c 色节点。换句话说如果我把树上所有 c 色节点都删掉剩下的树会碎成若干个连通块。如果 a 和 b 恰好落在同一个连通块里那么它们之间就存在一条完全不经过 c 色节点的路径。由于树上路径本身是唯一的这条不经过 c 色节点的路径就是原路径所以原路径上确实一个 c 色节点都没有。反过来如果 a 和 b 落在不同连通块里那说明任何一条连接 a、b 的路径都必须经过至少一个被删掉的 c 色节点。于是原路径上必然有目标颜色。这一个问题的转向直接把遍历路径变成了判断两个点是否在同一连通块里。后者正是并查集最擅长的领域。2.3 删掉一种颜色剩下的连通块说了算再深入说一步。对于一个固定的颜色 c我们可以把整棵树分成两类点颜色为 c 的点和颜色不为 c 的点。然后做一次思想实验把 c 色点全部从图上拿掉剩下的边只连接非 c 色点。这样一来非 c 色点就被分成了若干个连通块。我只需要给每个非 c 色点记录它属于哪一块查询时就能快速判断。有人可能会问路径上的 c 色节点可能不止一个删掉之后森林的形状会不会很复杂完全不用担心。树本身是连通的删掉若干个点之后剩下的部分一定是若干个互不相连的连通块。每个连通块内部的任意两个点之间原本的那条路径上不会有被删掉的点否则它们在这个森林里就不可能在同一个连通块里。这是树的一个非常漂亮的拓扑性质。这个观察是整个解法的基石也是这道题真正的考点。3. 银组推荐做法按颜色拆并查集3.1 两种颜色各建一个并查集既然颜色只有 G 和 H那我们就分别处理删掉 G 色节点和删掉 H 色节点两种情况。先处理 G。我建一个并查集 dsuG遍历整棵树的每条边如果这条边的两个端点都不是 G 色节点就把它们合并到同一个集合里。这样一来dsuG 里的每个连通块就对应着一块完全不含 G 色节点的连续区域。再处理 H。同理建 dsuH合并所有两端都不是 H 色节点的边。预处理只需要 O(N) 时间因为树只有 N-1 条边每种颜色扫一遍所有边就是 O(N)。这里有个细节并查集合并的是端点都不是目标颜色的边。也就是说如果某个节点本身就是目标颜色 c它不会被合并进任何区域在并查集里孤零零地自成一个集合。这正好对应删点后的森林形态c 色节点被删掉了但它们原本占用的位置在查询时要特殊处理。3.2 查询判断只有一行逻辑预处理完成后处理一次询问 (a, b, c) 只需要三步第一步看端点。如果节点 a 的颜色本来就是 c或者节点 b 的颜色本来就是 c那还犹豫什么路径上已经有一个目标颜色节点了直接输出 1。第二步如果 a 和 b 都不是 c 色节点就看它们在删掉 c 色节点后的并查集里是否属于同一个集合。属于同一个集合说明路径上完全没有 c 色节点输出 0不属于同一个集合说明路径上被 c 色节点隔开了输出 1。第三步把答案追加到字符串里。用伪代码写出来核心逻辑就一行if (color[a] c || color[b] c || find(a) ! find(b)) ans 1; else ans 0;注意第三项的 find(a) ! find(b) 只在 a、b 都不是 c 色时才调用对应并查集但写成上面的形式也完全没问题因为如果 a 或 b 是 c 色它俩根本不会被合并进非 c 色连通块find 结果大概率不相等最终结果同样是 1。为了逻辑严谨代码里我还是会先判断端点颜色。3.3 完整 C 代码下面是一份可以直接提交的 C17 代码。我建议你先把这份代码看懂再自己重新写一遍不要直接复制粘贴了事。#include bits/stdc.h using namespace std; struct DSU { vectorint fa; DSU(int n) { fa.resize(n 1); iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int a, int b) { a find(a); b find(b); if (a ! b) fa[a] b; } }; int main() { freopen(milkvisits.in, r, stdin); freopen(milkvisits.out, w, stdout); ios::sync_with_stdio(false); cin.tie(nullptr); int N, M; cin N M; string s; cin s; s s; vectorpairint, int edges; edges.reserve(N - 1); for (int i 0; i N - 1; i) { int x, y; cin x y; edges.push_back({x, y}); } DSU dsuG(N), dsuH(N); for (auto e : edges) { int u e.first, v e.second; if (s[u] ! G s[v] ! G) { dsuG.unite(u, v); } if (s[u] ! H s[v] ! H) { dsuH.unite(u, v); } } string ans; ans.reserve(M); for (int i 0; i M; i) { int a, b; char c; cin a b c; if (s[a] c || s[b] c) { ans.push_back(1); continue; } DSU dsu (c G) ? dsuG : dsuH; ans.push_back((dsu.find(a) ! dsu.find(b)) ? 1 : 0); } cout ans \n; return 0; }3.4 代码里的几个细节先说字符串下标。cin s 读进来的字符串第 0 个字符对应编号为 1 的农场。为了不让自己每次写 s[i-1] 看得眼晕我习惯在读完后执行s s。这样 s[1] 就是 1 号农场的颜色s[N] 就是 N 号农场的颜色跟节点的 1-indexed 编号完全对齐。这个习惯能省下不少低级错误。再说并查集的大小。节点编号从 1 到 N所以 DSU 内部数组要开 N1。iota(fa.begin(), fa.end(), 0)会把 fa[0] 到 fa[N] 全部初始化成自身。fa[0] 永远不会被用到但这样写起来省心。然后是预处理的方式。两种颜色的并查集可以放在同一个循环里遍历边省一次遍历。有人会问为什么不直接对每个颜色做 DFS因为并查集更简单不需要递归也不会爆栈。树只有 N-1 条边扫一遍把所有合法边合并得到的连通块和 DFS 完全一致。最后是查询部分。我先把端点颜色的判断放在前面因为这是最直接的特判。如果端点之一是 c 色直接给 1不用再管并查集。只有当两个端点都不是 c 色时才需要拿对应的并查集来判断连通性。这样维护下来的答案字符串最后统一输出一行符合题目要求。4. 进阶路线LCA 加树上前缀计数4.1 为什么还要提 LCA 做法并查集做法已经足够 AC 这道银组题但很多准备冲 Gold 的选手会问如果颜色不只有 G 和 H比如颜色有 10 种甚至更多并查集做法要做多少次预处理10 次、100 次吗每次都要遍历所有边虽然 O(KN) 在 K 很小的时候还能接受但如果 K 很大或者题目变成了查询路径上某种颜色的数量并查集思路就有点不够用了。这时候就需要 LCA 加树上前缀计数。这个做法更通用也是很多树论题的套路值得单独拿出来讲。4.2 树上路径颜色数的计算公式先把树以任意一个节点为根比如节点 1。DFS 一遍预处理每个节点的深度 depth[u]以及从根节点到节点 u 的路径上G 色节点数量和 H 色节点数量。这里我用两个数组记录前缀计数cntG[u]从根到 u 的路径上颜色为 G 的节点个数。cntH[u]从根到 u 的路径上颜色为 H 的节点个数。预处理是 O(N) 的很简单。查询的时候假设 LCA(a, b) l。那么从 a 到 b 的路径可以拆成 a 向上走到 l再向下走到 b 两段。路径上颜色 c 的节点总数等于cntC[a] cntC[b] - 2 * cntC[l] (color[l] c ? 1 : 0)这个公式的原理是cntC[a] 统计的是根到 a 的路径上颜色 c 的个数cntC[b] 统计的是根到 b 的路径上颜色 c 的个数。两者相加根到 l 的那一段被统计了两次所以要减去两倍的 cntC[l]。但 l 本身也被多减了一次所以最后要加回来判断 l 的颜色是不是 c。如果这个结果大于 0说明路径上存在目标颜色输出 1否则输出 0。4.3 倍增 LCA 的实现要点LCA 的实现方式有很多种倍增是最常见、也最不容易写错的一种。预处理阶段用 DFS 从根开始遍历记录每个节点的父节点 up[0][v] 和深度 depth[v]。然后递推 up[k][v] up[k-1][up[k-1][v]]表示从 v 往上跳 2^k 步到达的祖先节点。通常 k 取到 17 就够因为 2^17 131072超过 N 的上限更稳妥的做法是取 20 或者 60。查询 LCA 时先把深度较深的节点往上跳到和另一个节点同一深度然后从大到小枚举 k如果 up[k][a] ! up[k][b]就同时把 a 和 b 往上跳。最后两者父节点相同那个父节点就是 LCA。用前缀计数公式算出结果后判断是否大于 0。注意公式计算出来的可能是 0 或正整数只需要判断正负。4.4 两种做法的对比与选型建议我用一个表格来收束这两种方案维度并查集连通块法LCA 加前缀计数法预处理复杂度O(N)每个颜色扫一遍边O(N log N)DFS 加倍增预处理单次查询复杂度O(α(N))接近常数O(log N)空间复杂度O(N)O(N log N)核心难度思维转换LCA 模板熟练度颜色种类扩展每多一种颜色多扫一遍边每多一种颜色多一个前缀计数数组本道题适用性银组官方推荐极简完全可用偏进阶我的建议是如果你还在 Silver 阶段优先把并查集做法吃透它的思维价值很高代码量还小如果你已经在为 Gold 做准备LCA 做法也值得亲手实现一遍因为路径上的前缀计数思想会反复出现。两条路都走一遍这道题才算真正吃干抹净。5. 正确性证明与复杂度分析5.1 一个关键引理要证明并查集解法是对的只需要证明一个引理固定颜色 c。把树上所有 c 色节点删除后剩下的森林中两个非 c 色节点 u 和 v 属于同一个连通块当且仅当原树中 u 到 v 的简单路径上不包含任何 c 色节点。这个引理其实非常直观。如果 u 到 v 的路径上存在某个 c 色节点 x那么把 x 删掉后路径就在 x 的位置断开了u 和 v 不可能还连着。反过来如果 u 到 v 的路径上没有任何 c 色节点那么整条路径上的所有节点都不是 c 色这些节点在原树中本来就是一条连通的链删掉其他 c 色节点并不会影响它们之间的连通性所以 u 和 v 还在同一个连通块里。这个引理说明并查集里记录的非 c 色节点连通块恰好就是原路径是否经过 c 色节点的判据。5.2 查询判断的完整证明有了引理查询判断就迎刃而解。第一类情况a 或 b 本来就是 c 色节点。那么无论路径怎么走起点或终点已经是一个目标颜色节点路径上当然存在颜色 c。输出 1。第二类情况a 和 b 都不是 c 色节点。此时用删掉 c 色节点后的森林来判断。如果 a 和 b 在同一个连通块里根据引理原路径上不包含任何 c 色节点所以输出 0。如果 a 和 b 不在同一个连通块里根据引理原路径上至少包含一个 c 色节点所以输出 1。没有其他情况了。每一种分支都有明确的结论算法正确性也就清楚了。5.3 复杂度分析并查集解法的预处理阶段要遍历一次所有边来建图再对 G 和 H 各遍历一次所有边合并并查集。树的边数是 N-1所以预处理是 O(N)。查询阶段M 次询问每次只做常数次并查集 find 操作近似 O(M α(N))其中 α 是反阿克曼函数增长极慢可以看成常数。总复杂度 O(N M α(N))空间 O(N)。LCA 解法预处理是 O(N log N)每次查询 O(log N)总复杂度 O((NM) log N)。在本道题 NM1e5 的数据范围下两种解法都能轻松通过。区别只在于代码复杂度和思维路径。5.4 极端数据长什么样很多人担心算法在特殊数据下会不会失效这里试几个极端情况。第一种整棵树所有节点都是 G。查询 (a, b, G) 时端点必然是 G直接输出 1正确查询 (a, b, H) 时因为所有点都不是 HH 并查集会把整棵树合并成一个连通块两个端点 find 相同输出 0也正确。第二种整棵树是一条链。并查集照样把符合条件的边合并成若干连通块查询时 find 的结果完全由路径上的颜色分布决定不会因为树退化成链而变慢或出错。第三种查询中 a 和 b 相隔很远且路径上颜色交替。此时删掉目标颜色后a 和 b 往往会被隔到不同连通块find 不相等输出 1符合直觉。这些极端情况说明这个解法的正确性不依赖于树的形态也不依赖颜色分布的均匀程度是真正稳健的做法。6. 实测中最容易踩的六个坑6.1 字符串下标和节点编号错位这是我见过最多人犯的错误。题目里节点编号从 1 开始但 C 字符串下标从 0 开始。如果不做处理s[0] 会是 1 号农场的颜色s[N-1] 是 N 号农场的颜色。用 s[a] 去判断节点 a 的颜色时a1 查的是 s[1] 而不是 s[0]直接错位后果是全盘皆错。解决办法就是在读入字符串后执行s s;。这行代码看起来土但能保证后面的所有下标都跟节点编号对齐。6.2 并查集大小和初始化并查集数组如果开成 N那么 find(N) 就会越界在本地可能没事在评测机上会随机 RE。一定要开 N1。另外别忘了初始化iota(fa.begin(), fa.end(), 0)或者手写 for 循环把 fa[i] 设成 i。有一个常见的坑是只初始化到 N-1结果 find(N) 返回了一个没有初始化的值查出来的连通性完全随机。6.3 文件输入输出忘写USACO 提交题目时要求从 milkvisits.in 读入输出到 milkvisits.out。如果只写了标准输入输出本地跑得再欢提交后也会全错因为评测程序找不到输入文件。稳妥的做法是代码里直接写上freopen(milkvisits.in, r, stdin); freopen(milkvisits.out, w, stdout);本地测试时如果不想动文件可以临时注释掉这两行提交前取消注释。忘记这步的代价很高因为它不是逻辑错误而是 IO 错误不容易排查。6.4 答案是字符串不是换行分隔题目要求的输出格式是一行长度为 M 的字符串比如 01101而不是每行一个 0/1。有些选手习惯每次询问都 cout ans \n最后输出 M 行直接格式错误。正确做法是准备一个 string ans每次查询往里面 push_back(1) 或 push_back(0)最后统一输出一次换行。6.5 递归爆栈并查集解法没有递归天然避开了这个问题。但如果你选择 LCA 解法DFS 预处理时递归深度可能达到 N。在 N1e5 的链形数据下普通递归很容易爆栈。解决办法有两种一是用迭代 DFS 手写栈二是在本地编译时加栈空间参数比如在洛谷等平台可以用-Wl,--stack268435456但这不是比赛时的标准手段。更推荐的做法是学习一下非递归 DFS 或者用 BFS 预处理深度和父节点。6.6 查询条件写反判断端点颜色时正确写法是如果 s[a] c 或 s[b] c直接输出 1。有人会写成如果 s[a] ! c 且 s[b] ! c再判断并查集逻辑本身不算错但要小心漏掉端点本身就是目标颜色的情况。还有一种迷惑写法if (s[a] c || s[b] c || find(a) ! find(b))在 a 或 b 是 c 色时find 结果可能碰巧相等但前面两个条件已经为真整体结果还是 1。这种写法依赖短路求值能跑通但不直观建议还是拆开写避免给别人 review 代码时造成困惑。7. 从这道题带走的三个通用思路7.1 存在性查询转连通性查询这道题最重要的思维方式是把路径上有没有某类点转换成删掉某类点后两个端点是否连通。这个思路在很多树上问题里都能复用。比如判断一个点是否是路径上的必经点、判断路径是否经过某种颜色的区域、判断两个点之间是否有不经过某些点的替代路径都可能用上类似的转化。看到存在性三个字先想一想它的反面往往会有惊喜。7.2 离线按颜色处理第二种通用思路是离线按颜色处理。题目只有 G/H 两种颜色所以建两个并查集。如果颜色有 K 种就离线对每种颜色分别做一次预处理查询时按颜色分组回答。这个套路可以扩展到更复杂的属性比如节点有数字标签、有大小、有类别凡是路径上是否存在某个属性的查询都可以尝试按属性分组处理每组用合适的数据结构维护连通性。7.3 把树上的路径问题拆成删点后的森林最后一种思路是把树上路径和删点后的森林联系起来。删掉某些关键点后原树会碎成若干个连通块路径与关键点的关系就体现在两端点是否落在同一块里。这个视角在理解割点、桥、连通分量时也非常有用。虽然 Milk Visits 本身不要求你知道这些高级概念但做完这道题再回去看这些概念你会觉得它们没那么神秘本质上都是从删点后还连不连入手。这道题我前前后后写过三版。第一版暴力理所应当地超时第二版直接上树链剖分代码长到怀疑人生第三版想明白反向思路后用并查集二十几行就过了。后来每次遇到路径上是否存在某类点的题我都会先问自己一句反过来什么时候会不存在这个习惯帮我省下过不少冤枉代码。如果你也在准备竞赛希望这篇文章能帮你少走这一步弯路。