题意

给定一棵 $n$ 个结点的树，给每个结点赋一个 $[1, m]$ 的整数，满足：

$1$. 对任意两个不同结点 $u, v$，设它们路径上的结点数为 $l$（$l \ge 2$），路径上所有结点值的 LCM 不能被 $l$ 整除。 $2$. 所有结点值的 GCD 为 $1$。

求方案数，对 $998244353$ 取模。

---

结论

• 合法赋值中，至多一个结点的值大于 $1$。
• 若存在大于 $1$ 的值，它必须是某个质数的幂 $p^e$（$p$ 质数，$e \ge 1$，$p^e \le m$），其余结点全为 $1$。
• 全 $1$ 赋值总是合法（满足 $GCD=1$ 且对任意路径 $LCM=1$ 不被长度整除？注意：$LCM=1$，路径长度$≥2$，$1$ 不能被 $2$ 整除，成立）。

因此，总方案数 =

$$1 \ (\text{全 }1) \ + \sum_{p^e \le m} \ \sum_{x=1}^n [\,p^e \nmid (\operatorname{dist}(x,y)+1) \text{ 对所有 } y \neq x\,] $$

其中 $\operatorname{dist}(x,y)$ 是树上距离（边数），$路径结点数 = 距离+1$。

---

算法

$1$. 找到树的直径端点 $A, B$。 $2$. 对每个结点 $x$，计算 $\text{maxDist}[x] = \max(\operatorname{dist}(x,A), \operatorname{dist}(x,B)) + 1$，即 $x$ 到其它结点的最大路径结点数。 $3$. 统计每个距离值 $d$ 的结点个数 $\text{cnt}[d]$。 $4$. 预处理所有质数幂 $p^e \le m$。 $5$. 对每个质数幂 $pp$：

• 若 $pp > n$，则所有结点都合法（因为最大距离 $< pp$，$pp$ 不能整除任何距离），贡献 $n$。
• 否则，$坏结点数 = \sum_{k=1}^{\lfloor n/pp \rfloor} \text{cnt}[k \cdot pp]$，合法结点数 = $n - \text{坏结点数}$，贡献 $\text{合法结点数}$。 $6$. $答案 = 1 + \sum \text{贡献}$。

---

复杂度

$O(n \log n)$，空间 $O(n)$。

---

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int N = 1e6 + 5;

int n, m;
vector<int> g[N];
int dist[N];

void bfs(int s, vector<int>& d) {
    fill(d.begin(), d.end(), -1);
    queue<int> q;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 找直径端点
    vector<int> d1(n + 1), d2(n + 1);
    bfs(1, d1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    bfs(a, d1);
    int b = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    bfs(b, d2);

    vector<int> maxDist(n + 1);
    for (int i = 1; i <= n; i++) {
        maxDist[i] = max(d1[i], d2[i]);
    }

    // 统计每个距离的节点数
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cnt[maxDist[i]]++;
    }

    long long ans = 1; // 全1的情况

    // 预处理所有质数幂 <= m
    vector<int> primePowers;
    vector<bool> isPrime(n + 5, true);
    for (int i = 2; i <= n + 2; i++) {
        if (isPrime[i]) {
            for (long long j = 1LL * i * i; j <= n + 2; j += i) {
                isPrime[j] = false;
            }
            long long p = i;
            while (p <= m) {
                primePowers.push_back(p);
                if (p > m / i) break;
                p *= i;
            }
        }
    }
    sort(primePowers.begin(), primePowers.end());

    // 对每个质数幂，计算合法节点数
    for (int pp : primePowers) {
        if (pp > n) {
            // 所有节点都合法
            ans = (ans + n) % MOD;
        } else {
            int bad = 0;
            for (int d = pp; d <= n; d += pp) {
                bad += cnt[d];
            }
            int valid = n - bad;
            ans = (ans + valid) % MOD;
        }
    }

    cout << ans << "\n";

    return 0;
}