QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
[-9]

# 7839. 虹

Statistics

给定一棵 n 个点的树。

  • 称点集 S 连通,当且仅当 u,vS,所有 uv 的简单路径上的点均在 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]最小虹uS0,将 wu1
  • 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