CF842C Ilya And The Tree

Ilya 非常喜欢图，尤其是树。在他上次去森林时，Ilya 发现了一棵很有趣的树，这棵树的根节点是第 $1$ 个结点。树上的每个结点上都写着一个整数，第 $i$ 个结点写着 $a_{i}$。 Ilya 认为，第 $x$ 个节点的“美丽值”是从根节点到 $x$ 节点路径上所有结点（包括 $x$ 本身）上的数的最大公约数。此外，Ilya 可以将某一个结点上的数字修改为 $0$，或者对所有结点都不作改变。现在，他想要知道，对于每一个结点，能获得的最大可能的“美丽值”是多少。 对于每个节点，这个“美丽值”需要单独考虑。 根节点的美丽值等于它自身所写的数。

第一行包含一个整数 $n$，表示树上结点的数量（$1 \leq n \leq 2 \cdot 10^{5}$）。 第二行包含 $n$ 个整数 $a_{i}$（$1 \leq i \leq n$，$1 \leq a_{i} \leq 2 \cdot 10^{5}$），表示每个节点上写的数。 接下来的 $n-1$ 行中，每行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$，$x \neq y$），表示树中存在一条边 $(x, y)$。

输出 $n$ 个用空格隔开的整数，其中第 $i$ 个数表示第 $i$ 个结点能获得的最大可能美丽值。

由 ChatGPT 5 翻译