简单题。
先看到子树加和子树质数个数和，果断转换为 dfs 序进行处理。
既然有区间求和，考虑线段树。
若对于每一个节点维护一个 \(cnt\) 数组，用二进制数 \(x\) 来表示，即当 \(cnt_i = 1\) 时第 \(i\) 位为 \(1\)。设当前节点为 \(u\)，左右子节点分别为 \(ls\) 和 \(rs\)。发现 \(x_u = x_{ls} | x_{rs}\)。统计时，就是区间的所有 \(x\) 的按位或值 \(res\) 与质数数组所表示的二进制数 \(pr\) 的按位与后 \(1\) 的个数。然后考虑更改，令 \(v\) 为加的数，易得 x_u = (x_u << v & full) | (x_u >> (m - v))，其中 \(full = 2^m - 1\)，是防止溢出用的。
都到这一步了，不会还有人不知道怎么优化吧。
既然是二进制的数，用 bitset 进行优化即可。
时间复杂度：\(\mathcal{O}(\dfrac{nm\log n}{w})\)
代码：
const int N = 1e5 + 10, M = 1e3 + 10;
int n, m, Q, tot;
int a[N], b[N];
int tag[N << 2], d[N], siz[N], dfn[N], rdfn[N];
bitset<M> tr[N << 2], pr, f, ans;
int head[N], cnte;
struct edge {
int v, nxt;
} e[N << 1];
void adde(int u, int v) {
e[++cnte].nxt = head[u];
e[cnte].v = v;
head[u] = cnte;
}
void pushup(int u) {
tr[u] = tr[u << 1] | tr[u << 1 | 1];
}
void pushdown(int u) {
if (tag[u]) {
tag[u << 1] = (tag[u << 1] + tag[u]) % m, tag[u << 1 | 1] = (tag[u << 1 | 1] + tag[u]) % m;
tr[u << 1] = (tr[u << 1] << tag[u]) | (tr[u << 1] >> (m - tag[u]));
tr[u << 1 | 1] = ((tr[u << 1 | 1] << tag[u]) & f) | (tr[u << 1 | 1] >> (m - tag[u]));
tag[u] = 0;
}
}
void build(int u, int l, int r, int *a) {
if (l == r) {
tr[u].reset();
tr[u].set(a[l]);
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid, a), build(u << 1 | 1, mid + 1, r, a);
pushup(u);
}
void update(int u, int l, int r, int L, int R, int val) {
if (L <= l && r <= R) {
tag[u] = (tag[u] + val) % m;
tr[u] = ((tr[u] << val) & f) | (tr[u] >> (m - val));
return;
}
pushdown(u);
int mid = l + r >> 1;
if (L <= mid) update(u << 1, l, mid, L, R, val);
if (mid < R) update(u << 1 | 1, mid + 1, r, L, R, val);
pushup(u);
}
void query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R) {
ans |= tr[u];
return;
}
pushdown(u);
int mid = l + r >> 1;
if (L <= mid) query(u << 1, l, mid, L, R);
if (mid < R) query(u << 1 | 1, mid + 1, r, L, R);
}
void dfs_init(int u, int f) {
d[u] = d[f] + 1, siz[u] = 1, dfn[u] = ++tot, rdfn[tot] = u;
for (int i = head[u], v; i != 0; i = e[i].nxt)
if ((v = e[i].v) != f) {
dfs_init(v, u);
siz[u] += siz[v];
}
}
int main() {
ios
cin >> n >> m;
for (int i = 0; i < m; i++) f.set(i);
for (int i = 2; i < m; i++) pr.set(i);
for (int i = 2; i < m; i++)
if (pr[i]) {
for (int j = 2 * i; j < m; j += i)
pr.reset(j);
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i] %= m;
}
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adde(u, v), adde(v, u);
}
dfs_init(1, 0);
for (int i = 1; i <= n; i++) b[i] = a[rdfn[i]];
build(1, 1, n, b);
cin >> Q;
while (Q--) {
int opt, u, x;
cin >> opt >> u;
if (opt == 1) {
cin >> x;
update(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, x % m);
} else {
ans.reset();
query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
int res = (ans & pr).count();
cout << res << "\n";
}
}
return 0;
}