§ Description

Link.

给出一个带权无向图，边权为 $2^{a}\cdot3^{b}$ 形式。

给出 $q$ 组形如 $u,v,a,b$ 的询问，问 $u,v$ 中是否存在一条路径使得其边权之 $\text{lcm}$ 为 $2^{a}\cdot3^{b}$。

§ Solution

考虑 $\text{lcm}$ 的本质，对 $n$ 个数 $\prod_{i=1}^{k_{1}}p_{1,i}^{c_{1,i}},\prod_{i=1}^{k_{2}}p_{2,i}^{c_{2,i}},\dots,\prod_{i=1}^{k_{n}}p_{n,i}^{c_{n,i}}$ 取 $\text{lcm}$ 就是 $\prod_{i=1}^{\max\{k\}}p_{i}^{\max\{c\}}$（在一个数中存在的 $p$ 且在另一个中不存在的置为 $1$），对于这题即 $2^{\max\{a\}}\cdot 3^{\max\{b\}}$，让两个 $\max$ 分别等于题目给出的 $a,b$。

现在转化一下题意，在 $u,v$ 中选出一条可非简单路径使得 $\max\{a\},\max\{b\}$ 分别等于给出的 $a,b$。

有一个 naive 的想法是缩点后 LCT 维护结果发现不太行。（好像是我不行）

既然想到了用 LCT 维护连通性那么同样可以想到用 DSU 来维护，把所有满足条件的边放入一个 DSU 然后看 $u,v$ 是否能被这些边联通。

有两个关键字欸，我们离线询问排序吧。

把所有边按照 $a$ 排序，把询问按 $b$ 排序。

然后对边的标号分块，这样块内边 $a$ 有序。

然后把每个询问放在满足前面块的 $a$ 都小于等于这个询问的 $a$ 的块里，并且把块内询问 $b$ 排序，然后就可以做了。

代码狼 BH 今天又口胡题解没代码了。

Oops, something went wrong.