CF986E Prince's Problem

让我们以最近某部电影中的人物作为本题的主角。新复仇者联盟似乎引起了不少关注。我没有看过这个系列，也不太了解里面的英雄，但这并不妨碍我在题目描述中使用他们。所以，Thanos 和 Dr. Strange 正在做他们的超级英雄和超级反派的事情，突然他们遇到了一个普通的竞赛编程问题。 给定一棵有 $n$ 个顶点的树。 在每个顶点 $v$ 上有一个正整数 $a_v$。 你需要回答 $q$ 个询问。 每个询问的格式为 $u$ $v$ $x$。 你需要计算 $\prod_{w \in P} \gcd(x, a_w) \bmod (10^9 + 7)$，其中 $P$ 表示从 $u$ 到 $v$ 的路径上的所有顶点集合。换句话说，你需要计算从 $u$ 到 $v$ 的路径上所有顶点 $w$ 的 $\gcd(x, a_w)$ 的乘积。由于结果可能很大，请对 $10^9+7$ 取模。这里 $\gcd(s, t)$ 表示 $s$ 和 $t$ 的最大公约数。 注意，顶点上的数在所有询问中都不会改变。 我想你可能更感兴趣的是 Thanos 和 Dr. Strange 的超级英雄故事，而不是他们如何解决这个问题。所以，这道题就交给你来解决吧。

输入的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示树的大小。 接下来的 $n-1$ 行描述树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$）描述，表示 $u_i$ 和 $v_i$ 之间有一条边。保证这些边构成一棵树。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_v \le 10^7$）。 下一行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。 接下来的 $q$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $x_i$（$1 \le u_i, v_i \le n$，$1 \le x_i \le 10^7$），描述一次询问。

输出 $q$ 行，每行一个整数，依次表示每个询问的答案。每个答案对 $10^9+7=1000000007$ 取模。

由 ChatGPT 4.1 翻译