SP26843 INS16F - Who is the Best?

拜拉席恩家族是七国大地上最古老的家族之一。历代国王及继承人众多，他们的家谱结构可用一棵树来表示——每位角色都是树上的一个节点，初始值为瓦里斯大人分配的所谓「瓦里斯值」。你现在被任命为当前国王的分析师，任务是提供有关某个角色的深入分析。 国王给你下达了 **Q** 条命令，每条命令的类型如下： 1. 将从节点 **u** 到节点 **v** 的路径上所有角色的「瓦里斯值」乘以指定的数 **P**。 2. 针对某个具体角色 **X**，找出满足 **LCM(i, j)** 等于当前节点 **X** 的值的有序数对 (i, j) 的总数。 对于类型二的查询，需输出满足条件的数对个数，并对结果取模 **1000000007**。

第一行输入两个用空格分隔的整数 **N** 和 **Q**，分别代表角色的总数和需要处理的查询数。 接下来的 **N-1** 行中，每行有两个整数 **u** 和 **v**，表示角色 **u** 和角色 **v** 之间的亲属关系。 接着一行，有 **N** 个空格分隔的整数 $V_1, V_2, V_3, \ldots, V_N$，其中 $V_i$ 表示第 $i$ 个角色的「瓦里斯值」。 接下来是 **Q** 行，每行描述一个查询请求： - **1 u v P** - 第一类查询，更新路径上角色的值 - **2 X** - 第二类查询，分析当前节点的值

针对每个类型二的查询，在新的行里输出其结果。

- $1 \le N, Q \le 100,000$ - $1 \le u, v, X \le N$ - $1 \le V_i, P \le 1,000,000,000$ **本翻译由 AI 自动生成**