第一次看到 P6150 Clock Tree S 这题的时候我第一反应是这不就是个模拟题吗房间是一棵树每个房间挂着一个钟每次走到一个房间就把那里的钟拨快一小时问从哪些房间出发能想办法让所有钟都指向 12。按这个思路用 C 写了半小时 BFS然后看着状态数量陷入了沉思。后来我才发现这题真正考的压根不是搜索而是一个能压到 O(n) 的代数结论代码量可以短到 30 行以内。如果你正在练树上的思维题、准备月赛或者单纯被时钟这个包装搞晕了这篇文章会把从暴力到正解的完整推导链路讲清楚最后附上可以直接抄的 C 代码和暴力对拍方案。1. 题意拆到底这不是模拟是一道访问次数题1.1 钟面 12 小时天然是模 12 计数钟表只有 12 个刻度拨快一小时就是让当前指向的数字加 1并且 12 点之后又回到 1 点。所以每个钟的状态本质上是一个模 12 的计数器初始值是题目给的 a[i]读入范围 1 到 12每被访问一次就加 1最终要求变成 12也就是模 12 意义下的 0。这个模 12的视角非常重要。它意味着我们不关心某个钟被拨了多少次只关心次数对 12 取余的结果。设 cnt[v] 表示树上的点 v 在整个过程中被访问的总次数那可行性条件就是(a[v] cnt[v]) % 12 0稍微变形一下令need[v] (12 - a[v]) % 12那么问题就变成是否存在一条从某个起点 s 出发、在树上随意游走的路径使得每个点 v 的访问次数 cnt[v] 恰好满足cnt[v] % 12 need[v]这里要注意一个特别容易踩的坑need[v] 为 0 并不代表这个钟已经指向 12所以不能碰。它只代表这个点最终被访问的次数必须是 12 的倍数也就是说可以碰碰 12 次、24 次都行只要最后数对上就行。1.2 移动模型的形式化cnt[v] 与 need[v]我们把整棵树的节点编号为 1 到 n树的边是房间之间的走廊。一个移动方案可以看成是节点序列 v0, v1, v2, ..., vk其中 v0 s 是起点并且相邻两个节点之间必须有边。每个节点的访问次数说白了就是这个节点在序列里出现了多少次。注意起点 v0 也要算一次因为题目要求从起点房间出发时就会拨一次那个房间的钟。也就是说cnt[v] v 在序列 v0, v1, ..., vk 中的出现次数举个例子帮助理解。假设只有两个点 1 和 2之间有一条边。初始时钟 a[1]11a[2]12。也就是说点 1 需要被访问 1 次点 2 需要被访问 12 的倍数次。从点 1 出发如果只是走到点 2cnt[1]1cnt[2]1。点 1 的钟从 11 走到 12恰好满足点 2 的钟从 12 走到 1不满足。但如果我们继续在 1 和 2 之间来回走走一整圈 24 步最终停在点 1那么 cnt[1] 13cnt[2] 12模 12 之后分别是 1 和 0恰好满足。这个例子告诉我们两件事第一已经指向 12 的钟是可以被访问的只要最终访问次数是 12 的倍数第二解可能不是一条简单的路径而是一段需要绕很多圈的路线。这正是暴力搜索难受的地方。2. 暴力模拟为什么必然超时状态空间与无效路径2.1 朴素 BFS 的状态量级如果直接按照题意做 BFS状态至少需要记录两部分当前所在的节点编号以及每个钟当前指向几点。钟的状态有 12^n 种再乘上 n 个可能的当前位置总状态数是 n * 12^n。n 是几的时候这个数还能接受n4 的时候 12^4 20736可以跑n6 的时候就是 2985984勉强可以n10 的时候已经接近 620 亿直接爆炸。而树上的题 n 动不动给到几千这种暴力连边都摸不着。更麻烦的是即使剪枝也很难做。上一节那个两节点的例子告诉我们最优方案可能要走 24 步甚至更多如果每条边都可能需要绕 11 次来回短搜索大概率找不到解还会误判成从某个点出发不行。2.2 打破绕圈直觉基础路径 额外往返的分解树和普通图最大的区别是树上除了沿着边走没有其他回路。所谓回路只能表现为在某一条边上反复来回走。这是一个极其关键的观察。假设一次游走从 s 出发最终停在 t。把这个游走过程中所有反复横跳的部分从脑子里去掉剩下的必然是一条从 s 到 t 的简单路径。树上的额外绕圈本质上就是某些边被多走了若干个来回。于是任何游走方案都能拆成两部分先沿着 s 到 t 的唯一简单路径走一遍。这会使得路径上每一个点都被访问一次路径外的点访问 0 次。在若干条边上额外做往返。每在边 (u, v) 上走一个u - v - u的来回u 和 v 的访问次数都会增加 1而起点和终点都不变。这就是整道题的钥匙。它把找一条奇怪的游走序列转化成了给每条边分配一个额外的往返次数。额外往返次数并不是无限制的。因为每在一条边上走 12 个来回会让这条边的两个端点各增加 12 次访问在模 12 意义下等于什么都没发生。所以考虑每条边上的额外往返次数时只需要考虑 0 到 11 这 12 种取值更大没有意义。这个上界也给了我们一个额外的礼物如果有解那么总步数最多是基础路径长度不超过 n-1加上每条边最多 11 次往返每次往返 2 步。所以总步数有一个明确上界(n - 1) 2 * 11 * (n - 1) 23 * (n - 1)n 很小的时候这个上界完全可以用来做暴力搜索的深度限制后面对拍会用到。3. 一个代数结论把整道题压到 O(n)3.1 每棵子树向上需求的递推现在我们把问题变成纯粹的代数问题。设路径 s 到 t 是选定的基础路径cnt0[v] 表示基础路径带来的访问次数cnt0[v] 1如果 v 在 s 到 t 的路径上 cnt0[v] 0否则设每条边 e 上的额外往返次数为 k[e]那么每个点 v 在额外的往返中获得的次数等于所有与 v 相连的边的 k[e] 之和。最终要求cnt0[v] sum(与 v 相连的边上的 k[e]) ≡ need[v] (mod 12)定义一个需求差值 d[v]d[v] (need[v] - cnt0[v]) mod 12那么问题就变成能不能找到非负整数 k[e]使得对每个点 v所有与它相连的边的 k 值之和模 12 等于 d[v]。这个方程组看着很吓人但在树上有一个非常自然的消元方法。把树固定一个根不妨先取起点 s 为根。从叶子节点开始往上推。叶子节点只有一个父边所以父边的 k 值直接被叶子节点的 d 值唯一确定。确定之后把这个值带给它的父节点父节点把需求 d 减去所有子边已经确定的 k 值剩下的就是它自己往上连接父节点的边的 k 值。这样一路推到根如果根的需求和所有子边的 k 值之和对不上说明无解。用公式表示设 g[v] 表示v 到父节点那条边上的 k 值那么有g[v] ≡ d[v] - sum(所有 v 的子节点 c 的 g[c]) (mod 12)从叶子往上算每个 g 都会被唯一确定。把这个递推式反复展开会发现一个漂亮的性质g[v] 等于 v 子树内所有 d 值按深度奇偶性交替相加。写成式子就是g[v] sum_{u 在 v 的子树中} (-1)^{dist(v, u)} * d[u]最终根节点的自洽条件就是 g[root] ≡ 0根没有父边但可以把根也想象成有一条虚拟父边。于是整个起点 s 是否可行的判断变成一条简洁的等式。3.2 只和深度奇偶性有关的 S 值继续化简。根的一致性条件是0 ≡ sum_{u 全体点} (-1)^{dist(s, u)} * d[u]因为推导时我选了起点 s 作为根所以 dist(s, u) 就是深度。把 d[u] need[u] - cnt0[u] 代进去分成两项0 ≡ sum_u (-1)^{dist(s,u)} * need[u] - sum_{u 在 s 到 t 路径上} (-1)^{dist(s,u)}第一项只和起点 s 有关记为 A(s)。第二项是路径上所有点的交替和从 s距离 0出发符号 1、-1、1、-1 交替。这个交替和特别简单如果 dist(s, t) 是偶数整段路径长度是偶数交替和等于 1如果 dist(s, t) 是奇数交替和等于 0。也就是说A(s) 只能等于 0 或者 1并且分别对应终点 t 距离起点为奇数或偶数。这时再用一个树上距离和深度的经典关系两个点之间的距离奇偶性等于它们深度奇偶性的异或。换句话说(-1)^{dist(s,u)} sign[s] * sign[u]其中 sign[x] 表示x 到根节点的距离为偶数时取 1为奇数时取 -1。于是 A(s) 可以写成A(s) sign[s] * S其中S sum_u sign[u] * need[u]S 是一个只和整棵树、以及 chosen 根有关的全局值。更妙的是它只需要一次 DFS 就能算出来每到一个点根据深度的奇偶给 need 加或者减。通过这个式子每个点 s 的 A(s) 只可能是 S 或者 -S。这样我们就不用枚举起点和终点了。3.3 最终判定表与直觉解释把所有情况列成一张表假设我们以 1 号点为根做 DFS算出来的 S 已经取模到 0 到 11S 模 12 的值可行性0全部点都可行但 n1 的特殊情况除外1深度为偶数的点可行11也就是 -1深度为奇数的点可行其他值没有任何点可行这个结论初看非常反直觉尤其是所有钟都已经指向 12的时候S 0结果竟然所有点都是可行的。实际上确实如此我们只需要选择终点是该点的一个相邻点然后把每条边上的往返次数做出合适的分配就可以让每个点的访问次数都变成 12 的倍数。两个点都指向 12 的例子已经验证了这件事。用逐点判断可以规避 n1 的边界坑对每个点算出自己的 A(s)如果 A(s) 1可行如果 A(s) 0 且 n 2也可行。这是因为当 A(s) 0 时我们需要找一个距离 s 为奇数的终点 t而只要树上节点数大于 1s 就至少有一个邻居距离正好是 1所以一定找得到。4. C 实现代码很短坑都在细节里4.1 完整代码#include bits/stdc.h using namespace std; const int MAXN 2505; vectorint g[MAXN]; int a[MAXN], needVal[MAXN], depth[MAXN]; int n; long long S 0; void dfs(int u, int fa, int d) { depth[u] d; if (d 1) { S - needVal[u]; } else { S needVal[u]; } for (int v : g[u]) { if (v fa) continue; dfs(v, u, d ^ 1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin a[i]; needVal[i] (12 - a[i]) % 12; } for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0, 0); S (S % 12 12) % 12; int ans 0; for (int i 1; i n; i) { int A; if (depth[i] 1) { A (12 - S) % 12; // 奇数深度点A -S } else { A S; // 偶数深度点A S } if (A 1) { ans; } else if (A 0 n 2) { ans; } } cout ans \n; return 0; }这段代码的逻辑非常短。DFS 遍历一遍算出 need 的交替和 S再遍历所有点根据深度奇偶性得到对应的 A最后统计可行起点数。4.2 为什么不需要换根有读者可能会问DFS 的根我是随便选的 1 号点如果换一个根每个点的深度奇偶性不是变了吗S 的值不会变吗确实会变。比如换成根 r 之后每个点到 r 的距离奇偶性和原来到 1 的距离奇偶性整体差了一个固定的 sign[r]所以新的 S 等于 sign[r] * S。但每个点自己的 A(s) 始终等于原来的 sign[s] * S和根选谁没有关系。起点 s 的判定只依赖 A(s)所以答案不会因为根不同而变化。因此在代码实现里任意选一个根做 DFS 都是安全的不需要写换根 DP。4.3 取模负数与 n1 等边界C 里负数取模的结果可能是负数比如-1 % 12在大多数编译器里是 -1。所以算完 S 之后一定要先转成正数再使用S (S % 12 12) % 12;否则后面判断A 1会出问题。n1 的时候也要小心。如果只有一个点并且 a[1] 12那么 need 0S 0。按全部点都可行的口径很容易直接输出 1但事实上只有一个点且不能移动起点访问一次之后这个钟就从 12 变成 1根本不可能回到 12。所以代码里必须加上n 2这个条件。如果 a[1] 11need 1S 1这个起点就可行因为访问一次之后刚好到 12。输入输出方面题目数据量不算大但为了保险还是加上ios::sync_with_stdio(false)和cin.tie(nullptr)避免因为输入输出拖慢速度。5. 对拍验证用暴力搜索确认结论正确5.1 小数据暴力搜索怎么写代数结论漂亮归漂亮但竞赛里最怕的就是推导过程有一个隐蔽的符号错误。我的习惯是写一个针对 n 很小的暴力搜索和 O(n) 正解对拍。暴力搜索的思路很简单枚举所有起点DFS 枚举移动序列。唯一需要小心的就是步数上限。前面推导过如果有解总步数不会超过 23 * (n - 1)。n ≤ 4 的时候上限不超过 69所以暴力搜索把步数限制在 80 甚至 100 都是安全的。暴力搜索的核心代码大致如下bool bruteCheck(int pos, int limit, vectorint clockVal) { bool allZero true; for (int i 1; i n; i) { if (clockVal[i] ! 0) allZero false; } if (allZero) return true; if (limit 0) return false; for (int nxt : g[pos]) { clockVal[nxt] (clockVal[nxt] 1) % 12; if (bruteCheck(nxt, limit - 1, clockVal)) return true; clockVal[nxt] (clockVal[nxt] 11) % 12; } return false; }注意在调用暴力之前先给起点拨一次也就是clockVal[s] (clockVal[s] 1) % 12然后再进入 DFS。这样每次都枚举下一步走到哪个相邻点就足够覆盖所有移动方案。把 1 到 12 的初始时钟值随机生成配合 n ≤ 4 的随机树跑几百组数据和正解对比。只要暴力说可行而正解说不可行或者反过来就说明推导或者代码出了问题。我自己用这个方式对拍没有发现不一致的情况。5.2 我自己测过的几组自造数据这里列出几组自己构造的边界数据方便你直接复制到程序里验证。第一组两个点2 11 12 1 2need[1] 1need[2] 0。以 1 为根S 1 - 0 1。深度偶数点有 1 号所以答案是 1。手算也确实只有从 1 号出发能成功。第二组两个点且都指向 122 12 12 1 2need 全是 0S 0。n 2所以两个点都是可行起点。答案是 2。这组数据最反直觉但通过代数结论可以清晰判断。第三组单点1 11need 1S 1答案是 1。如果改成1 12need 0S 0n 1答案是 0。第四组三个点链3 12 12 12 1 2 2 3need 全 0S 0n 2所以答案是 3。也就是说即使所有钟都已经指向 12从任意一个点出发都存在一种绕圈方案让所有钟最终都还是 12。这些数据虽然简单但每一个都能帮我们检查代码里最容易出错的地方负数取模、n1 的边界、以及全 0 不代表不可行这个反直觉的结论。6. 复盘这道题真正的考点Clock Tree S 这道题最让我感慨的地方是代码写出来只有 30 行但推导过程中绕了好几个弯。如果一上来就想着模拟游走过程很容易陷在绕圈的细节里出不来。核心的思维跳跃在于把走一条路径改写成基础路径 每条边上的额外往返次数。这个改写天然适合树因为树上没有别的环路。从这题里总结出来的经验以后遇到类似的在树上走来走去能否达到某个状态的题我会优先考虑先把每个点的状态数量压缩成模数这里就是模 12。把游走拆成简单路径和边上往返两部分。给每条边设一个变量用树形递推从上往下确定变量。最后看根节点会不会自洽把可行性浓缩成一个全局值。另外还有一个实操技巧遇到这种结论很短的题不要急着直接提交先写一个 n ≤ 4 的暴力搜索随机生成数据对拍。哪怕只能跑很小的数据也能帮你拦截掉大量符号错误和边界错误。对拍几百组毫无问题之后再把正解交上去心里会踏实非常多。如果你在赛场上真的遇到这题记得提醒自己钟表上的 12 点就是模 12 的 0所有绕圈都可以化成边上的往返次数当你发现自己对着一个模拟题无从下手的时候往往不是题目变难了而是该换一个数学视角看它了。