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

题意：给定一棵树和数组 $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;
}