题目理解

我们有一个无向图，每条边的权值可以表示为 $2^a \cdot 3^b$。
对于每个查询 $(u, v, a, b)$，需要判断是否存在一条从 $u$ 到 $v$ 的路径，使得路径上所有边权的最小公倍数恰好等于 $2^a \cdot 3^b$。

关键点：

• 路径可以不是简单路径（可以重复经过边和点）
• 边权只有两个质因子：$2$ 和 $3$
• 最小公倍数 = 所有边权中 $2$ 的最大指数 × 所有边权中 $3$ 的最大指数

---

问题转化

设路径经过的边集为 $E'$，则： [ \text{lcm}(E') = 2^{\max_{e \in E'} a_e} \cdot 3^{\max_{e \in E'} b_e} ] 因此，问题转化为：

是否存在一条 $u$ 到 $v$ 的路径，使得路径上边的 $a$ 最大值等于 $a$，$b$ 最大值等于 $b$

---

暴力方法的困难

直接对每个查询 BFS/DFS：

• $n, q \leq 50000$，$m \leq 100000$
• 每个查询 $O(m)$ 会超时
• 总复杂度 $O(qm)$ 不可行

---

离线处理 + 并查集

我们可以使用离线处理和并查集来高效回答所有查询。

核心思路：

将边和查询都按某种顺序处理，利用并查集维护连通性以及每个连通分量的 $(a_{max}, b_{max})$。

---

算法设计：双关键字分块

由于有两个维度 $a$ 和 $b$，我们可以：

1. 对边按 $a$ 排序，对查询也按 $a$ 排序
2. 将边分成若干块，每块内 $a$ 值相近
3. 对每块内的边，再按 $b$ 排序
4. 使用回滚莫队的思想处理查询

具体步骤：

步骤1：预处理

• 将边按 $a$ 排序
• 将查询按 $a$ 排序
• 设定块大小 $B = \sqrt{m}$ 或根据实际情况调整

步骤2：处理每个 $a$ 块

对于当前 $a$ 块 $[L, R]$：

1. 找出所有 $a$ 查询值在该块内的查询
2. 将这些查询按 $b$ 排序
3. 初始化并查集（包含 $a < L$ 的所有边）
4. 按 $b$ 递增顺序处理查询：
   • 添加 $b \leq$ 当前查询 $b$ 的边（在当前 $a$ 块内）
   • 检查 $u$, $v$ 是否连通，且连通分量的 $(a_{max}, b_{max})$ 是否等于查询的 $(a, b)$
   • 回滚并查集到当前状态

---

并查集维护的信息

每个连通分量需要记录：

• 父节点信息（用于路径压缩）
• 连通分量的 $max\_a$, $max\_b$
• 大小（用于按秩合并）

合并两个连通分量时：

max_a_new = max(comp1.max_a, comp2.max_a)
max_b_new = max(comp1.max_b, comp2.max_b)

---

回滚莫队实现

由于需要回滚操作，我们使用可回滚并查集：

• 记录每次合并操作
• 回滚时逆向执行这些操作

struct DSU {
    vector<int> parent, size;
    vector<pair<int, int>> max_ab; // (max_a, max_b)
    vector<tuple<int, int, int, int>> history; // 操作记录
    
    DSU(int n) : parent(n), size(n, 1), max_ab(n, {-1, -1}) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
    }
    
    bool unite(int x, int y, int a, int b) {
        x = find(x), y = find(y);
        if (x == y) {
            // 更新最大值
            auto [old_a, old_b] = max_ab[x];
            max_ab[x] = {max(old_a, a), max(old_b, b)};
            history.emplace_back(-1, x, old_a, old_b); // 记录回滚信息
            return false;
        }
        
        if (size[x] < size[y]) swap(x, y);
        
        // 记录合并前状态
        history.emplace_back(y, x, max_ab[x].first, max_ab[x].second);
        
        parent[y] = x;
        size[x] += size[y];
        max_ab[x] = {
            max({max_ab[x].first, max_ab[y].first, a}),
            max({max_ab[x].second, max_ab[y].second, b})
        };
        return true;
    }
    
    void rollback(int checkpoint) {
        while (history.size() > checkpoint) {
            auto [y, x, old_a, old_b] = history.back();
            history.pop_back();
            
            if (y == -1) {
                // 回滚最大值更新
                max_ab[x] = {old_a, old_b};
            } else {
                // 回滚合并操作
                parent[y] = y;
                size[x] -= size[y];
                max_ab[x] = {old_a, old_b};
            }
        }
    }
    
    int get_checkpoint() { return history.size(); }
};

---

复杂度分析

• 排序：$O(m \log m + q \log q)$
• 分块：$O(\sqrt{m})$ 块
• 每块处理：$O(\sqrt{m} \cdot (m + q) \cdot \alpha(n))$
• 总复杂度：$O(\sqrt{m}(m + q) \alpha(n))$，可接受

---

样例验证

输入：

4 5
1 2 1 3
1 3 1 2
1 4 2 1
2 4 3 2
3 4 2 2
5
1 4 3 3
4 2 2 3
1 3 2 2
2 3 2 2
1 3 4 4

处理过程：

• 对于查询 $(1,4,3,3)$：存在路径 $1 \to 2 \to 4$，最大 $a=3$，最大 $b=3$ → Yes
• 对于查询 $(2,3,2,2)$：无法同时达到 $a=2$ 和 $b=2$ → No

输出：

Yes
Yes
Yes
No
No

符合样例。

---

优化技巧

1. 块大小调整：根据 $m$ 和 $q$ 的关系调整块大小
2. 路径压缩优化：在可回滚并查集中使用按秩合并而非路径压缩
3. 查询预处理：提前过滤明显不可能的查询

---

总结

本题的关键在于：

1. 将最小公倍数问题转化为双关键字最大值问题
2. 使用离线处理 + 分块降低复杂度
3. 实现可回滚并查集支持查询回滚
4. 注意边界条件和特殊情况的处理

这是一个典型的数据结构+离线算法问题，考察了对复杂查询处理和数据结构的综合应用能力。