链接： G. Yash And Trees

题意：
给一棵以 1 为根的树，每个点都有一个权值，有两种操作：

1. 给 以 x 的子树下的节点权值增加 v 。
2. 查询 x 的子树下有多少个点的权值 a[i] % m 为素数。

思路：

1. 观察到 m 的范围只有 1000 ， 可以用二进制记录 每个数是否出现过，即线段树的每个节点表示 1000 个数出现了哪些 ， 这样 pushup还是很好写 ，就是两个子区间的 | 值。这里用一个 bitset 存值就好了。和一个题目很类似 D. Distinct Characters Queries
   这个题是求区间内出现的字母的个数，也是同理。这里为什么不直接用数表示二进制状态呢 ，因为这里有 1000位 ，肯定是超过 ll 限制 了 , bitset 就可以直接开 1000 位，并且也能进行二进制运算。
2. 然后感觉难的地方就是修改了 ， 每个数增加 v ，仔细想想想其实就是把二进制数左移 v 位，就相当于这个区间每个数都增加 了 v ，但是还要考虑 取模的操作 ，其实就是再 | 上这个数右移 （mod - v ) 位 。也就是sum[rt] = (sum[rt] << v) | (sum[rt] >> (mod - v) );模拟一下就明白了 。
3. 最后得到的答案是这个区间出现了哪些数 ，再判断出现了多少个素数就好了，也可以直接用 bitset 保存有哪些素数 和得到的答案 & 一下 也是可以的。

代码：

#include<iostream>
#include<cstdio>
#include<map>
#include<math.h>
#include<bitset>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=4e5+7;
ll la[maxn];
bool isprime[maxn];
int n,mod,a[maxn],q;
bitset<1007> sum[maxn],ans;
int num,head[maxn],tot = 1,le[maxn],ri[maxn],id[maxn];
struct node{int to,next;
}e[maxn];
void sieve(){for(int i=0;i <= 1000;i++)isprime[i]=true;isprime[0]=isprime[1]=false;for(int i = 2;i <= 1000;i ++){if(isprime[i]){for(int j= 2 * i ; j <= 1000;j += i){isprime[j]=false;}}}
}
void add(int u,int v){e[num].to = v;e[num].next = head[u];head[u] = num ++;
}
void dfs(int u,int pre){le[u] = tot ++;id[tot - 1] = u;for(int i = head[u];i != -1; i = e[i].next){int to = e[i].to;if(to == pre) continue;dfs(to,u);}ri[u] = tot;
}
void pushup(int rt){sum[rt] = sum[rt << 1] | sum[rt << 1 | 1];
}
void change(int rt, int v){sum[rt] =  (sum[rt] << v) | (sum[rt] >> (mod - v) );
}
void pushdown(int l,int r,int rt){int mid = (l + r) / 2;if(la[rt] == 0) return ;la[rt << 1] = (la[rt << 1] + la[rt]) % mod;la[rt << 1 | 1] = (la[rt<<1|1] + la[rt]) % mod;change(rt << 1 , la[rt]);change(rt << 1 | 1 ,la[rt]);la[rt] = 0;
}
void build(int l,int r,int rt){if(l == r){sum[rt].set(a[id[l]]);return ;}int mid = (l + r) / 2;build(l , mid ,rt<<1);build(mid + 1 , r , rt << 1|1);pushup(rt);
}
void update(int L,int R,int val , int l,int r,int rt){if(L <= l && R >= r){change(rt,val);la[rt] = (la[rt] + val) % mod;return ;}pushdown(l , r, rt);int mid = (l + r) / 2;if(L <= mid) update(L , R , val , l , mid , rt << 1);if(R > mid) update(L, R , val ,mid + 1, r ,rt << 1 | 1);pushup(rt);
}
bitset<1007> query(int L ,int R ,int l,int r,int rt){bitset<1007> s ;s.reset();if(L <= l && R >= r){return sum[rt];}pushdown(l,r,rt);int mid = (l + r) / 2;if(L <= mid) s |= query(L , R ,l , mid ,rt<<1);if(R > mid) s  |= query(L ,R ,mid+1 , r , rt<<1|1);return s;
}
int main(){sieve();scanf("%d%d",&n,&mod);memset(head,-1,sizeof(head));for(int i = 1; i <= n ; i ++){scanf("%d",&a[i]);a[i] %= mod;}for(int i = 1,u,v; i < n; i ++){scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs(1,-1);build(1,n,1);scanf("%d",&q);while(q--){int op,x,y;scanf("%d",&op);if(op == 1){scanf("%d%d",&x,&y);y %= mod;update(le[x],ri[x] - 1, y,1,n,1);}if(op == 2){scanf("%d",&x);ans = query(le[x],ri[x] - 1 ,1 , n, 1);int s = 0;for(int i = 0; i < mod; i ++){if(ans[i] == 1 && isprime[i]) s ++;}printf ("%d\n",s);}}
}