思路

• 关键性质：对于权值集合的最小公倍数，若把每个数按素数分解 $w=\prod p^{e_p}$，则 LCM 对应每个素数的指数取最大值。由于 $w_i \le 100$，素数仅有 $25$ 个（不超过 $97$），各指数极小（如 $2$ 的最大指数为 $6$）。

• 路径查询：仅为根到 $x$ 的路径。用重链剖分将路径拆成 $O(\log n)$ 个链段。

• 数据结构：用一棵线段树，节点维护一个长度为 $25$ 的小数组，表示该区间所有黑色节点对每个素数的指数最大值（白色为全零）。

  • 翻转颜色 → 点更新（设为该点的指数向量或全零）。
  • 查询根到 $x$ → 若干区间查询，合并（逐素数取最大），最后计算

题目内容

给定一棵以节点 $1$ 为根的有 $n$ 个节点的树，每个节点 $i$ 有一个正整数权值 $w_i$ ，初始被涂成黑色或白色。你需要支持以下两种操作；

1.翻转节点 $x$ 的颜色(黑色变白色，自色变黑色)；

2.查询从根节点 $1$ 到节点 $x$ 的路径上所有黑色节点的权值的最小公倍数(若路径上无黑色节点，则记为 $1$ )

【名词解释】