好懂的做法，更大的常数。

题意：给定一棵树和数组 $a$，有一个指针，指针可以从 $u$ 向相邻点 $v$ 走一步（可以重复经过点），并使 $a_v \gets (a_v + 1) \bmod 12$，求有多少个指针的起点可以满足指针走完任意步后可以使数组 $a$ 的值全部变为 0。

对于一个根节点为 $u$ 的树，树的大小为 $siz_u$，$u$ 的儿子分别是 $v_i$、$v_2$、……、$v_{siz_u}$。假设此时指针走边 $u \to v_i$，则分两种情况：

1. 指针不再回到 $u$ 点，此时边 $u \to v_i$ 会比边 $v_i \to u$ 多走一次；

2. 指针回到 $u$ 点，此时边 $u \to v_i$ 和 边$v_i \to u$ 走的次数一样多。

于是成了经典的树上背包模型，我们定义 $f(u, i, k, x)$ 表示以 $u$ 为根，前 $i - 1$ 棵子树的 $a$ 都变为0，此时指针走第 $i$ 棵子树，走完后需满足 $a_{v_i} = k$，且指针是否回到 $u$（0 表示回，1 表示不回）的可行性。

转移显然。

$$f(u, i, k, 0) = \lor _ {x=0} ^ {12} \{ f(u, i - 1, (k - x) \bmod 12, 0) \land f(v, siz_v, (-x) \bmod 12, 0) \} \\ \\ f(u, i, k, 1) = \lor _ {x=0} ^ {12} \{ f(u, i - 1, (k - x) \bmod 12, 0) \land f(v, siz_v, (-1 - x) \bmod 12, 1) \} \\ \\ f(u, i, k, 1) = \lor _ {x=0} ^ {12} \{ f(u, i - 1, (k - x) \bmod 12, 0) \land f(v, siz_v, (-1 - x) \bmod 12, 0) \} \\ \\ f(u, i, k, 1) = \lor _ {x=0} ^ {12} \{ f(u, i - 1, (k - x) \bmod 12, 1) \land f(v, siz_v, (-x) \bmod 12, 0) \}$$

滚掉 $i$ 一维就是标准树上背包的写法了。

贴一下代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e3 + 5;
int n, a[N];
vector<int> G[N];
bool f[N][12][2], g[12][2];
void dfs(int u, int ufa) {
    f[u][a[u] % 12][0] = 1;
    for (int v : G[u]) if (v != ufa) {
        dfs(v, u);
        memcpy(g, f[u], sizeof(g));
        memset(f[u], 0, sizeof(f[u]));
        for (int k = 0; k < 12; k++)
            for (int x = 0; x < 12; x++) {
                f[u][k][0] |= g[(k - x + 12) % 12][0] & f[v][(12 - x + 12) % 12][0];
                f[u][k][1] |= g[(k - x + 12) % 12][0] & f[v][(11 - x + 12) % 12][1];
                f[u][k][1] |= g[(k - x + 12) % 12][0] & f[v][(11 - x + 12) % 12][0];
                f[u][k][1] |= g[(k - x + 12) % 12][1] & f[v][(12 - x + 12) % 12][0];
            }
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    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;
        G[u].push_back(v), G[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        memset(f, 0, sizeof(f)), dfs(i, 0);
        ans += (f[i][0][0] || f[i][0][1]);
    }
    cout << ans << '\n';
    return 0;
}

但是洛谷老爷机过不了。原因：看似是 $O(N ^ 2)$，实际上 有 $12 \times 12 \times 2$ 个常数，总共 $2500 \times 2500 \times 12 \times 12 \times 2 = 1.8 \times 10 ^ 9$操作数。

于是考虑优化。注意到转移方程是类似于 bitset 优化的东东，直接把 $k$ 那一维压成一个 int 直接做位运算即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2.5e3 + 5;
int n, a[N], f[N][2], g[2];
vector<int> G[N];
int mov(int t, int i) { return (t >> i) | ((t & (1 << i) - 1) << 12 - i); } // 改为将第i位为开头
void dfs(int u, int ufa) {
    f[u][0] = 1 << a[u], f[u][1] = 0;
    for (int v : G[u]) if (v != ufa) {
        dfs(v, u);
        g[0] = f[u][0], g[1] = f[u][1], f[u][0] = f[u][1] = 0;
        for (int k = 0; k < 12; k++) {
            f[u][0] |= bool(mov(g[0], k) & mov(f[v][0], 0)) << k;
            f[u][1] |= bool(mov(g[0], k) & mov(f[v][1], 11)) << k;
            f[u][1] |= bool(mov(g[0], k) & mov(f[v][0], 11)) << k;
            f[u][1] |= bool(mov(g[1], k) & mov(f[v][0], 0)) << k;
        }
    }
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], 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);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        dfs(i, 0), ans += (f[i][0] & 1 || f[i][1] & 1);
    cout << ans << '\n';
    return 0;
}

因为题目求起点有多少个，那么我们依次枚举每个点作为起点，把它当做树根，从它出发往孩子走，看看能不能做到。

每当Farmer John沿着一条线在树上走的时候，遇到的每个点时间都往前加1。考虑从树上某个结点u走到它的孩子v，那么u和v上的时间都往前加1了。也就是说要改就父子一起改，父子之间的差是不变的。既然题目中是验证是否能完成，我们不妨贪心地看，每次不停地从父子之间来回走，直到把孩子改成12，这时候根据父子差固定，我们就能知道u现在是多少。然后再去搞下一个孩子，再确定u的值。直到把所有孩子都改好，此时u固定到了某个数。回到上一层，再由父亲把u改成12

那么这么一轮下来，最后除了根，其他点都是12了。那么根如果正好是12，说明是可以的。如果根不是12呢？其实根是1也行，因为这样就最后的时候从根的最后一个孩子停下，不走回来。这时候根和最后一个孩子的时间会差一个。除了这两种情况，其他都不行。

这样枚举每个点做根，每次根确定以后，一遍dfs，总的时间复杂度是$O(n^2)$，不超时。实际写的时候，用一个c数组表示每个点现在的时间，然后用0表示12，这样每次对12取模就行了，写起来比较方便。最终目标也是把所有点调成0.

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;
const int MAXN = 2505;
int n, c[MAXN], t[MAXN], ans;
vector<int> adj[MAXN];

void dfs(int u, int f) {
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == f) continue;
        //先递归孩子，把孩子调到0
        dfs(v, u);
        //当前点和孩子的差不变，求出当前点的值
        t[u] = (t[u] - t[v] + 12) % 12;
    }
}

int main() {
//    freopen("clocktree.in","r",stdin);
//    freopen("clocktree.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c[i]);
        c[i] %= 12;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        //先把c数组拷贝到t数组里面，去操作t数组。免得c被改掉了下次循环数不对了。
        memcpy(t, c, sizeof(t));
        dfs(i, 0);
        //最后根上剩下0或者1就是可以的
        if (t[i] == 0 || t[i] == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}

后记，后来比赛完才想起来有个O(n)的二分染色算法，其他大佬写过题解了，我就不写了。