给定一棵 n 个点的树。
- 称点集 S 连通,当且仅当 ∀u,v∈S,所有 u 到 v 的简单路径上的点均在 S 中。
- 称点集 S 是 [l,r] 的虹,当且仅当 S 连通,且 S 包含 [l,r] 中的所有点。
- 称点集 S0 是 [l,r] 的最小虹,当且仅当 S0 是 [l,r] 的所有虹中大小最小的。可以证明,S0 是唯一的。
点带权,点 u 的权值为 wu,初始所有点权均为 0。同时,给定序列 {z1,z2,⋯,zn}。
给定 q 次命令,每次命令形如以下两类之一:
1 l r
:令 S0 为 [l,r] 的最小虹,∀u∈S0,将 wu 加 1。2 l r u
:求 (∑ri=l19901991zgcd 的值。
输入格式
第一行两个正整数 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 。