Clock Tree[USACO 2020 February Silver]
题意
一个 $n$ 个点的树，点有点权 $a_i$，每次选择一个相连的点，每走一次到该点，该点的点权变为 $(a_i+1)\bmod k$。
可以从任意点开始，任意点结束，能重复经过多次。
问有多少个出发点，满足最后存在一种方案使得点权均为 $0$。
原题：$n\leq 2500,k=12$
加强版：$n\leq 2\times 10^6,k\leq 10^9$。
题解
Part 0:$n\leq 2500$，必须走回出发点
首先必须明白一点，如果一条边的两端点全是 $0$，我们也还是可以走的。因为来回走 $k$ 次不就好了嘛。
假设枚举出发点，然后以该出发点为根。看子树内是否满足。
比较像树形DP的形式。
考虑DP的本质，是将一个大问题变成若干个子问题。
能否设置一个状态，表示子树内，除了这个点以外的点全变为 $0$ 后，该点还要变多少次才能变为 $0$。
转移的时候让父亲和儿子相互抵消，使得儿子变为 $0$，然后父亲此时的状态可以 $O(1)$ 计算。
显然是可以的。设为 $f_i$。
那么有：$f_u\equiv -a_u-\sum_{v\in son_u}f_v(\bmod k)$
最后必须满足 $f_{root}$ 为 $0$ ，$root$ 才能满足条件。
枚举 $root$，$O(n)$ 树形DP，计算是否可行。
Part 1:$n\leq 2500$
是否能把上面的思路转移过来呢？
试一下吧。
还是枚举根节点（出发点）。
考虑最后一次经过根节点的情况，如果要满足条件，那么只能剩下一条 $k-1$ 的链，且此时根节点为 $0$。
如图所示：
那么可以发现，如果让链上最后两个 $k-1$ 相互抵消，那么一直抵消下去，最后最多剩下一个 $k-1$，再让这个 $k-1$ 和根节点相互抵消，此时根节点变为了 $1$。也就是说，根节点还需要 $k-1$ 次才变为 $0$。这种情况也是可以的，即 $f_{root}=k-1$。
时间复杂度 $O(n^2)$。
到这里就做完了原题。
Part 2:$n\leq 10^6$
显然换根DP就好了。
时间复杂度 $O(n)$，需要两遍dfs，常数有点大。
Part 3:$n\leq 2\times 10^6$
考虑转移方程到底是什么：$f_u\equiv -a_u-\sum_{v\in son_u}f_v(\bmod k)$。
假设以 $1$ 为根节点。
那么处于奇数层的 $u$ 的贡献是 $+a_u$，偶数层的 $u$ 的贡献是 $-a_u$。
而显然偶数层的点的最终答案是一样的。
奇数层的答案是偶数层的相反数。
因此直接暴算就好了，维护一下层数的奇偶性，就dfs也不用了。
这还是树形DP吗？
注意 $n=1$ 的特判。
时间复杂度 $O(n)$。
程序
1 |
|