QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
统计

给定一棵 $ n $ 个点的树。

  • 称点集 $ S $ 连通,当且仅当 $ \forall u,v \in S $,所有 $ u $ 到 $ v $ 的简单路径上的点均在 $ S $ 中。
  • 称点集 $ S $ 是 $ [l,r] $ 的,当且仅当 $ S $ 连通,且 $ S $ 包含 $ [l,r] $ 中的所有点。
  • 称点集 $ S_0 $ 是 $ [l,r] $ 的最小虹,当且仅当 $ S_0 $ 是 $ [l,r] $ 的所有中大小最小的。可以证明,$ S_0 $ 是唯一的。

点带权,点 $ u $ 的权值为 $ w_u $,初始所有点权均为 $ 0 $。同时,给定序列 $ \{z_1,z_2,\cdots,z_n\} $。

给定 $ q $ 次命令,每次命令形如以下两类之一:

  • 1 l r:令 $ S_0 $ 为 $ [l,r] $ 的最小虹,$ \forall u \in S_0 $,将 $ w_u $ 加 $ 1 $。
  • 2 l r u:求 $ \left(\sum_{i=l}^r 19901991^{z_{\gcd(i,u)} w_i} \right) \bmod {20242024} $ 的值。

输入格式

第一行两个正整数 $ n,q $。

第二行 $ n $ 个非负整数,依次表示 $ z_1,z_2,\cdots,z_n $。

接下来 $ n-1 $ 行,每行两个正整数 $ u,v $,描述一条树上从 $ u $ 到 $ v $ 的边。

最后 $ q $ 行,每行 $ 3 $ 或 $ 4 $ 个正整数,描述一次命令。

输出格式

对于每次询问(即第二类命令)输出答案。

样例一

input

5 4 1 0 0 0 1 1 2 1 3 3 4 3 5 1 2 3 2 1 3 3 1 4 5 2 3 5 3

output

19561959 19561959

限制与约定

本题采用捆绑测试

对于所有测试数据保证:$ 1 \le n, q \le 8 \times 10^4,0 \le z_i \le 10^9 $,所有命令满足 $ 1 \le l \le r \le n, 1 \le u \le n $,保证第一类命令的 $ (l,r) $ 随机生成。随机生成方式如下:

  • 在 $ [1,n] \cap \mathrm{Z} $ 中等概率随机生成 $ l $。
  • 在 $ [1,n] \cap \mathrm{Z} $ 中等概率随机生成 $ r $。
  • 若 $ l>r $,则交换 $ l,r $。
子任务编号分值$ n \le $$ q \le $特殊性质子任务依赖
$ 1 $$ 10 $$ 10^3 $$ 10^3 $
$ 2 $$ 20 $$ 65536 $$ 65536 $A, B
$ 3 $$ 20 $$ 65536 $$ 65536 $A依赖于子任务 $ 2 $
$ 4 $$ 30 $$ 65536 $$ 65536 $依赖于子任务 $ 1,2,3 $
$ 5 $$ 20 $$ 80000 $$ 80000 $依赖于子任务 $ 1,2,3,4 $

特殊性质 A:保证所有第二类命令均在所有第一类命令之后。

特殊性质 B:保证第二类命令次数 $ \le 20 $。