USACO Silver Milk Visits：树上路径存在性查询的并查集与LCA解法

如果你在准备 USACO Silver 组，2019 年 12 月的这道 Milk Visits 是绕不开的经典题。名字很温馨，农场、奶牛、牛奶，骨子里却是一道标准的树上路径查询问题：给你一棵 N 个节点的树，每个节点标记成 G 或 H，再给你 M 次询问，每次问从节点 a 到节点 b 的简单路径上，存不存在标记为 c 的节点。N 和 M 都到 1e5，指望每个询问都去 DFS 一遍路径，基本是送死。这道题非常适合刚学完并查集、想往树论方向进阶的选手，它没有复杂的模板堆砌，却能让人真正理解"存在性查询"和"连通性"之间的等价关系。这篇文章会把题意、两种主流解法、正确性证明和调试经验一次讲透。

1. 题目读法和题意还原

1.1 输入输出到底长什么样

题目给的信息很简洁。第一行两个整数 N 和 M，N 是农场数量，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，所以第一问输出 0；1 到 3 路径上有 H，输出 1；4 到 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)。当 N=M=1e5 时，这是 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++ 代码

下面是一份可以直接提交的 C++17 代码。我建议你先把这份代码看懂，再自己重新写一遍，不要直接复制粘贴了事。

#include <bits/stdc++.h> using namespace std; struct DSU { vector<int> 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; vector<pair<int, 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 内部数组要开 N+1。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 两种做法的对比与选型建议

我用一个表格来收束这两种方案：

我的建议是：如果你还在 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((N+M) log N)。在本道题 N=M=1e5 的数据范围下，两种解法都能轻松通过。区别只在于代码复杂度和思维路径。

5.4 极端数据长什么样

很多人担心算法在特殊数据下会不会失效，这里试几个极端情况。

第一种，整棵树所有节点都是 G。查询 (a, b, G) 时，端点必然是 G，直接输出 1，正确；查询 (a, b, H) 时，因为所有点都不是 H，H 并查集会把整棵树合并成一个连通块，两个端点 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 的颜色时，a=1 查的是 s[1] 而不是 s[0]，直接错位，后果是全盘皆错。

解决办法就是在读入字符串后执行s = " " + s;。这行代码看起来土，但能保证后面的所有下标都跟节点编号对齐。

6.2 并查集大小和初始化

并查集数组如果开成 N，那么 find(N) 就会越界，在本地可能没事，在评测机上会随机 RE。一定要开 N+1。另外别忘了初始化，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。在 N=1e5 的链形数据下，普通递归很容易爆栈。解决办法有两种：一是用迭代 DFS 手写栈，二是在本地编译时加栈空间参数，比如在洛谷等平台可以用-Wl,--stack=268435456，但这不是比赛时的标准手段。更推荐的做法是学习一下非递归 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 本身不要求你知道这些高级概念，但做完这道题再回去看这些概念，你会觉得它们没那么神秘，本质上都是从"删点后还连不连"入手。

这道题我前前后后写过三版。第一版暴力，理所应当地超时；第二版直接上树链剖分，代码长到怀疑人生；第三版想明白反向思路后，用并查集二十几行就过了。后来每次遇到"路径上是否存在某类点"的题，我都会先问自己一句：反过来，什么时候会不存在？这个习惯帮我省下过不少冤枉代码。如果你也在准备竞赛，希望这篇文章能帮你少走这一步弯路。