企业官网建设流程全解析

打卡信奥刷题（2998）用C++实现信奥题 P6150 [USACO20FEB] Clock Tree S

如果你也跟我一样在信奥刷题里一天一天打卡，那么第2998篇来了：P6150 [USACO20FEB] Clock Tree S。别看它顶着USACO的编号，实际上是一道非常适合练“树上计数+模运算”的题：给你一棵树，每个房间里挂着一个显示1到12的钟，从任意房间出发，每走到一个房间，那个房间的钟就往前拨1小时，12会跳回1，问有多少个出发点可以通过一系列移动，最终让所有钟都指向12。

这题范围不大，N最多只有2000级别，所以最笨也最稳的思路就是枚举每个点当起点，各自做一遍深度优先搜索，O(N^2)也完全能过。不过它的难点不在代码量，而在为什么要做DFS、DFS返回什么、最后为什么判断0或11。这篇文章就把这几件事彻底讲清楚，同时给一份可以直接提交的C++实现，再把我踩过的几个坑一并放在后面，建议看完自己动手敲一遍。

1. 先看懂题目在问什么

1.1 把“钟表故事”转成数学条件

题目给一棵树，节点数是N，边数是N-1。每个节点有一个初始时钟值a[i]，范围是1到12。你从某个节点s出发，每一步可以移动到相邻节点，到达节点后，那个节点的钟值加1，并且12加1会变成1，也就是说所有计算都在模12下进行。你可以来回走任意多次，最后所有钟都指向12时算成功，停止时不需要回到起点。

问有多少个不同的s可以做到。

直接模拟路径肯定没法做，因为路径长度没有上限。但既然是模12，走到某个节点的次数多12和没有走效果一样。我们需要知道的只是每个节点最终被访问了多少次，并且只关心这个次数除以12的余数。

1.2 必须先算清楚的“缺口”

令每个节点初始为a[i]，要变成12，它一共需要被拨快多少次？

设d[i] = (12 - a[i]) % 12。

这个d[i]就是节点i的“缺口”。比如初始钟是1，需要拨快11次；初始钟已经是12，需要0次。注意不是12次，因为12点已经是目标状态。

于是，问题变成了：是否存在一条从s出发、最后停在任意点的walk，使得每个节点i的访问次数v[i]满足：

v[i] ≡ d[i] (mod 12)，对所有i成立。

后面的所有分析都围绕这个同余方程展开。

2. 核心思路：树上路径访问次数怎么配平

2.1 每条边被走过几次，决定了访问次数

树上的路径有个很优雅的奇偶结构。假设起点是s，终点是t。把从s到t的简单路径叫做P，那么：

• P上的边，因为要从s那一侧走到t那一侧，走过的总次数一定是奇数；
• 不在P上的边，进入那棵子树以后，为了回到原来的部分，必须成对往返，走过的总次数一定是偶数。

更进一步，如果一条边被走了偶数次，那它给两个端点带来的“进入次数”一定相同；如果被走了奇数次，那么终点t方向一侧的端点会多一次进入。

换句话说，某条边走奇数次的集合，恰好就是从s到t的一条路径。这条路径给路径上除了起点s以外的每个点都额外带来1次访问。

这是后面理解“最后不回家”的关键。

2.2 从叶子往上推：为什么DFS能唯一确定答案

如果固定了一个根（也就是起点s），那么树上的边和点都变得层次清晰。假设我们先不考虑“最后不回家”这件事，就要求走一条从s出发回到s的欧拉式路线，那么所有边都会被走过偶数次，没有一条路径是特殊的。

这时候，每个节点的访问次数由边上走的“次数的一半”决定。我们想知道：能不能给每条边分配一个经过次数，使得每个节点恰好满足自己的缺口d[i]？

这看起来变量很多，但树给了我们一个超强的性质：叶子节点只有一条边连着父亲，所以叶子节点的需求直接决定了这条边需要提供多少次访问。只要叶子定了，它父亲这边就要扣掉这笔贡献；扣完之后，父亲又相当于新的“叶子”，继续往上传。这个过程一直进行下去，直到根节点。

于是我定义DFS返回值：

dfs(u)表示：以u为根的这一棵子树，在内部所有边都配平之后，u还需要通过它到父亲的那条边，向父亲传递多少次贡献。

计算方式就是：

• 先给自己留d[u]的需求；
• 枚举每个孩子v，调用dfs(v)，得到孩子子树传给u的值；
• 从d[u]里减掉所有孩子的返回值；
• 对12取模，返回。

写成代码就是：

int dfs(int u, int fa) { int cur = (12 - a[u]) % 12; for (int v : adj[u]) { if (v == fa) continue; cur = (cur - dfs(v, u) + 12) % 12; } return cur; }

为什么用“减”？因为对于一个非根节点u，如果它的孩子v返回了一个值g，说明边(u,v)为了满足v子树的需求，需要给v那边贡献g。可这条边同时也会牵动u这边，从u的角度看，这条边已经“用掉”了g的额度，所以u自己的剩余需求要减掉这个g。这样一层一层推上去，每一个非根点的返回值其实都被子树唯一确定了。

2.3 根节点没有父亲，所以要看“余额”

根节点没有父亲边，没办法把需求传递给任何人。所以在上面这个向上推的过程结束后，根节点剩下的值必须为0，方程才完全配平。

我把根节点最终得到的值记作val。

如果val == 0，那么恭喜，从根出发最后回到根，存在一种走法能让所有钟都指向12。

但为什么很多解法里面，val == 11也能算可行？

这就是“最后不回家”的修正：原本要求每条边走偶数次，形成一个从根出发且回到根的闭环。现在你允许最后停在一个节点t，那从根到t这条路径上的边就从“走两次”变成了“走一次”。相比闭环，根会少一次被访问，而t以及路径上的其他非根节点会多一次访问。

重点来了：这件事到底会把根的余额修掉多少，和t的深度有关。逐层往上推可以证明，根余额的变化量只可能是0或1。如果终点t到根的距离是偶数，根余额不变；如果是奇数，根余额会加1，也就是在模12下从11变成0。

所以：

• val == 0：直接采用闭环方案即可；
• val == 11：只要树里存在一个奇数深度的节点，就把它当作终点，正好把-1修成0；
• 其他val值：无论选哪个终点都修不平，这个起点不可行。

任何一棵至少有两个节点的树，从根出发总能找到深度为1的相邻节点，奇数深度终点必然存在。唯一的特殊场景是N=1，那时候没有相邻节点，val==11不能算可行。

2.4 一个小例子帮助理解

拿两个点举例，节点1和节点2相连，a[1]=10，a[2]=11。d[1]=2，d[2]=1。

枚举起点1：以1为根，叶子2返回1，根余额val=d[1]-1=1。既不是0也不是11，所以起点1不可行。试一下也确实不行：无论如何走，两个点的访问次数永远是相等或者差1，凑不出(2,1)这个组合。

枚举起点2：以2为根，叶子1返回2，根余额val=d[2]-2=-1，也就是11。因为N>1，存在奇数深度终点1，所以可行。实际走法：从2出发走到1，1的钟从10到11；再走回2，2的钟从11到12；最后从2走到1，1的钟从11到12，停在1。完美。

这个例子说明：同一个树，有的点能当起点，有的点不能，不能一拍脑袋只判断val==0。

3. C++实现：枚举起点DFS就能AC

3.1 建图和DFS函数

N只有2000，用邻接表vector存树足够。DFS直接递归写，不用担心栈深度。核心难度就是不要搞错模12运算。

注意C++里取模负数是负数，比如(5 - 9) % 12等于-4，不是8。每次做完减法都要先加12再模12，保证结果落在0到11之间。

我一开始就在这里吃过亏，把cur写成cur = (cur - dfs(v, u)) % 12，最后结果各种乱飘。正确写法：

cur = (cur - dfs(v, u) + 12) % 12;

这个+12可能是负数的两倍也不怕，因为12和0模12等价，就算结果是负数+12还是负，也顶多再补一次，但实际范围下+12已经足够。

3.2 完整可提交代码

#include <bits/stdc++.h> using namespace std; const int MAXN = 2005; int n; int a[MAXN]; vector<int> adj[MAXN]; // 返回以u为根、fa为父节点时，u需要在父边上“补”多少 int dfs(int u, int fa) { int cur = (12 - a[u]) % 12; for (int v : adj[u]) { if (v == fa) continue; cur = (cur - dfs(v, u) + 12) % 12; } return cur; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } int ans = 0; for (int s = 1; s <= n; s++) { int val = dfs(s, 0); // 0：闭环可行 // 11：需要最后停在奇数深度节点，只有 n==1 时没有这样的节点 if (val == 0 || (val == 11 && n > 1)) { ans++; } } cout << ans << '\n'; return 0; }

代码非常短，但每一步都对应前面的推导。不要小看这么短的程序，它能过只是因为N小；如果N到10万级别，就需要换根DP优化了，这点后面再说。

3.3 几个容易写错的边界

第一，a[i]等于12时，(12 - 12) % 12是0，表示它不需要被访问。有人会习惯性写成(12 - a[i])，得到0没有问题；但如果你去求(12 - a[i]) % 12，C++会正确返回0。真正容易错的是你在心里把12当成“转一圈需要12”，然后判断val==12，那在模12体系下就是0，会全盘错。

第二，N=1。只有一个点的时候没有边可以走，唯一可行情况是这个点初始就是12。上面代码里dfs(1,0)会返回(12-a[1])%12，初始是12就返回0，否则返回操作数；配合(n > 1)条件，不会误判。

第三，递归函数里每个起点都要重新DFS，所以要用bool或vis标记吗？不需要，因为我们是在树上做父亲参数传递，天然不会走回头路。只要传fa，所有节点最多被访问一次，整个DFS是O(N)。

4. 常见问题与排查技巧实录

4.1 四个最容易阴到你的问题

4.2 为什么网上有人说答案是0或-1，代码里却写11

这是同一个东西。11在模12下就是-1。if(val == 11)和if(val == -1 % 12)本质上等价，但C++里-1%12还是-1，不落在0到11之间，所以最稳妥还是判断11。

我当时对着题解纠结了很久：自己推出来是-1，别人写的是11，到底谁错了？后来想明白模12余数通常统一成0到11，-1写做11，这是约定问题。代码里写val==11更直观，不用额外处理负数。

4.3 为什么不是“所有d[i]之和能被12整除就可行”

树不是完全图，访问次数不是每个点独立分配的。边上走的次数会同时影响两个端点，所以全局和虽然是一个必要条件，却不是充分条件。

例如两个点a=[10,11]，d之和=3，显然不是12的倍数，起点2却可行。原因在于起点2的终点选择给根带来的修正，让两个点的实际访问次数组合变成了(2,1)。全局和的约束不够强。

这道题真正需要考虑的是每个节点“连出去的边上分配的访问次数”，边的分配又受叶子约束逐步唯一确定。所以DFS向上推，比简单求和可靠。

4.4 递归深度和常数优化

N=2000时递归深度最多2000层，C++默认栈足够，不需要手写栈。如果你把N改成200000，一是O(N^2)会超时，二是递归200000层可能爆栈，需要改成用栈模拟或换根DP。

做题时先看数据范围再定方案。这道题N小，枚举起点是常规正解，不要为了炫技写一个复杂的二次扫描。

5. 这类树上游走题的做题心得

5.1 把“路径次数”变成“边上的未知数”

树上游走问题最常见的一个突破口就是：不要试图枚举路径，而是考虑每条边走几次。一条边从走到另一次，实际上给两个端点分别带来的访问次数是确定的。树的边数比点数少一，所以叶子的限制会把所有未知数逐步定死，最后只剩根上的一个“余额”等待判断。

这种处理方式在USACO这类树上计数题里非常常见，名字可能叫“叶子消元”或“树上DP”。本质就是解一个线性方程组，只不过模数是12，且方程结构是树形的。

5.2 做题时一定要手算小样例

我刷题有个习惯，任何结论都会先手算N=2和N=3的例子验证一遍。这道题如果不手算两个点的那个反例，很容易把判断条件写成val==0，然后对着正确答案发呆半小时。

手算的时候不要拿大样例，就自己造两个点、三个点、一条链、一棵星形树，暴力枚举所有可能的移动方式也不复杂。把这些小样例喂进DFS，观察返回值，多种几轮基本就能理解题意和结论。

5.3 别死在“模12”的细节上

整个题绕不开12。取模的每个中间值都要保证落在0到11；判断答案时0和11是两个合法值；初始已经是12的点缺口是0而不是12。这些细节非常琐碎，但恰恰是AC和WA的分界线。

我把自己的检查清单固定在代码注释里：先看输入范围，再看取模符号，最后看特殊n=1，基本不会再翻车。

最后再分享一个小技巧：如果你记不住为什么val==11也合法，就记住这句话——“根还差一次光临，那就最后一步走一条单程，停在一个奇数深度的房间门口。”走单程会让根少被拜访一次，终点多被拜访一次，这个一进一出正好把11修成0。下次再遇到这道题，哪怕忘了完整推导，也能凭这句话把判断条件写对。做题多了你会发现，很多“树上访问次数”的题目都隐藏着类似的单程修正逻辑，理解了它，比背代码有用得多。