CF633G Yash And Trees

Yash 喜欢玩树，尤其是当问题和质数相关时他会非常激动。在他 20 岁生日时，他收到了一个有 $n$ 个点的有根树，并需要在该树上回答若干查询。听说在树上玩质数的游戏后，Yash 实在太兴奋了，于是请你来帮忙回答相关查询。树的根为节点 $1$。每个节点 $i$ 都有一个权值 $a_i$。另外，给定一个整数 $m$。 有两种类型的查询： 1. 给定节点 $v$ 和整数 $x$，将以 $v$ 为根的子树内所有 $a_i$ 增加 $x$； 2. 给定节点 $v$，你需要求满足以下条件的质数 $p$（$p

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100000, 1 \leq m \leq 1000$）——树的节点数和题目中的整数 $m$。 第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$）——各节点的初始权值。 接下来 $n-1$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条边连接的节点编号。 下一行包含一个整数 $q$（$1 \leq q \leq 100000$）——查询的数量。 接下来的 $q$ 行，每行是以下两种格式之一： - `1 v x`，表示第一类查询（$1 \leq v \leq n, 0 \leq x \leq 10^9$）； - `2 v`，表示第二类查询（$1 \leq v \leq n$）。 保证至少有一个第二类查询。

对于每一个第二类查询，输出满足条件的质数个数。

由 ChatGPT 5 翻译