问题分析

我们有一棵 $N$ 个节点的树，其中 $N-2$ 条边的边权已知，一条边的边权不确定（在 $[L,R]$ 范围内）。对于不确定边权的每个可能取值，需要计算树中所有路径的 $\gcd$ 为 $1$ 的点对数量。

关键难点：

• 需要高效处理不确定边权的所有可能取值
• 路径 $\gcd$ 的计算涉及整棵树的边权

算法思路

核心思想：莫比乌斯反演 + 并查集

利用莫比乌斯反演将 $\gcd = 1$ 的条件转化为可计算的形式，并通过并查集维护连通性信息。

主要步骤

1. 莫比乌斯函数预处理

mu[1] = 1;
for (int i = 2; i < N; i++) {
    if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
    for (int j = 1; j <= cnt && i * pri[j] < N; j++) {
        vis[i * pri[j]] = 1;
        if (i % pri[j]) mu[i * pri[j]] = -mu[i];
        else {
            mu[i * pri[j]] = 0;
            break;
        }
    }
}

2. 固定边权的路径统计

对于已知的 $N-2$ 条边，使用并查集按因子分解统计路径：

for (int d = 1; d <= 100000; d++) {
    for (int i = d; i <= 100000; i += d)
        for (auto it = e[i].begin(); it != e[i].end(); ++it)
            uni(pnt[*it - 2], pnt[*it - 1]);
    
    for (auto it = s.begin(); it != s.end(); it++) {
        if (*it == fa[*it])
            res += siz[*it] * (siz[*it] - 1) / 2 * mu[d];
        // 重置并查集
        fa[*it] = *it;
        siz[*it] = 1;
    }
    s.clear();
}

3. 不确定边的处理

不确定边将树分成两个连通分量 $A$ 和 $B$。对于边权 $w$：

• 分量内部的路径已经在前一步计算（存储在 res 中）
• 跨分量的路径：$\gcd(\text{path}_A, \text{path}_B, w) = 1$

使用莫比乌斯反演处理跨分量路径：

// 对两个分量分别DFS计算gcd分布
dfs(rt1, 0, 0, 0);
dfs(rt2, 0, 0, 1);

// 莫比乌斯反演计算跨分量路径数
for (int opt = 0; opt < 2; opt++) {
    for (int i = 1; i <= 100000; i++) {
        sum[opt][i] = t[opt][0];
        for (int j = i; j <= 100000; j += i)
            sum[opt][i] += t[opt][j];
    }
}

for (int i = 1; i <= 100000; i++)
    sum[0][i] *= sum[1][i];

for (int i = 1; i <= 100000; i++)
    for (int j = i; j <= 100000; j += i)
        ans[j] += sum[0][i] * mu[i];

算法原理

莫比乌斯反演应用

利用恒等式：

$$\sum_{d|\gcd(\text{path})} \mu(d) = \begin{cases} 1 & \text{if } \gcd(\text{path}) = 1 \\ 0 & \text{otherwise} \end{cases}$$

将 $\gcd = 1$ 的路径计数转化为：

$$\text{ans} = \sum_{\text{path}} \sum_{d|\gcd(\text{path})} \mu(d) = \sum_{d=1}^{M} \mu(d) \cdot (\text{gcd被d整除的路径数}) $$

并查集的作用

对于每个因子 $d$，只保留边权能被 $d$ 整除的边，然后用并查集统计连通分量大小，计算路径数。

不确定边的处理

设不确定边权为 $w$，跨分量路径的 $\gcd$ 条件为：

$$\gcd(\gcd(\text{path}_A), \gcd(\text{path}_B), w) = 1 $$

通过预处理两个分量的 $\gcd$ 分布，可以快速计算对于每个 $w$ 的答案。

复杂度分析

• 莫比乌斯筛：$O(M \log \log M)$，其中 $M = 10^5$
• 并查集操作：$O(M \log M \cdot \alpha(N))$，其中 $\alpha$ 是反阿克曼函数
• DFS和统计：$O(N + M \log M)$
• 总复杂度：$O(M \log M + N)$，能够处理 $N, M \leq 10^5$ 的数据

代码结构

1. 输入处理：读取树结构和不确定边信息
2. 莫比乌斯预处理：筛法计算莫比乌斯函数
3. 固定边统计：使用并查集统计已知边的贡献
4. 分量分析：DFS计算两个分量的gcd分布
5. 反演计算：莫比乌斯反演计算跨分量路径
6. 答案输出：结合固定部分和变化部分输出最终答案

总结

本题通过巧妙的莫比乌斯反演和并查集技术，将复杂的路径gcd统计问题转化为可高效计算的形式。算法充分利用了数论性质和数据结构，在合理复杂度内解决了大规模数据下的查询问题。

关键技术：莫比乌斯反演、并查集、因子分解、树上统计