住在拔作岛上的贫测机该如何是好

· · 题解

联考 NOIP T4，由于莫反细节写错导致 100 \to 0，赫赫，原题 600ms 神人卡常，联考时限放宽数据范围缩小放过虚树做法还是太有素质了。值得一提的是该假做法成功通过你谷非 Subtask 3 随机数据以外的所有数据，/bangbangt。

先把 LCA 限制去掉，我们考虑求出 f_p 表示满足条件的 u,v 在 p 子树内的 a_u \times a_v 的总和，那么 b_p=f_p-\sum_{q \in \text{son}(p)} f_q。

然后用莫反把 \gcd 限制去掉。要求不互质数对乘积和，转而考虑求互质数对乘积和。我们考虑一个弱化叫做给定一个序列 \{a_n\} 求出其中所有互质数对乘积和。显然值域上开个桶，接着莫反直接做。具体而言，记 m 为值域，s_i 表示值为 i 的数的总和，那么答案为 \displaystyle\sum_{i=1}^m s_i \sum_{j=1}^m s_j [\gcd(i,j)=1]。莫反后变成 \displaystyle \sum_{i=1}^m s_i \sum_{k\mid i}\mu(k) \sum_{k \mid j} s_j，于是我们先求出 g_k=\sum_{k|i} s_i，然后对每个 i 枚举因数莫反。把上述过程放到树上就是对每颗子树做，需要支持动态加入一个数求莫反答案，和上述过程本质相同，然后用 dsu on tree 维护求出 f_p 做到 \mathcal O(d(m)n\log n)。堂堂倒闭 TLE。一个 naive 的优化是注意到如果 \mu(i)=0 那么他对答案毫无贡献.所以因数只枚举 \mu(i) 非零的部分，可以一开始用调和级数复杂度预处理因数 vector。\mu(i) 非零的因数个数即为每个质因子只出现 0/1 次的因数个数，至多 2^{\omega(m)}=64 次，复杂度 \mathcal O(n2^{\omega(m)}\log n)，轻微卡常就可通过。

卡常小技巧：处理 \mu(i) 非零的因数时不考虑不在原序列内出现过的数，然后轻松通过。

#include <bits/stdc++.h>
#define ull unsigned long long
#define uint unsigned int
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int M = 5e5 + 10;
const uint MOD = 998244353;
int n, m = 5e5, A[N]; vector<int> G[N];
int prime[M], ptot; uint mu[M]; bool is[M], vis[M];
vector<int> D[M]; int cnt[M];
void Sieve() {
    mu[1] = 1;
    for (int i = 2; i <= m; i ++) {
        if (!is[i]) { mu[i] = MOD - 1, prime[++ ptot] = i; }
        for (int j = 1; j <= ptot && i * prime[j] <= m; j ++) {
            is[i * prime[j]] = 1, mu[i * prime[j]] = (MOD - mu[i]) % MOD;
            if (i % prime[j] == 0) { mu[i * prime[j]] = 0; break; }
        }
    } 
    return ;
}

uint cur = 0, sum[M], Ans[N];
int sz[N], hson[N], dfn[N], R[N], dfncnt, inv[N]; uint W[N];
void DFS1(int u, int f) {
    sz[u] = 1; dfn[u] = R[u] = ++ dfncnt; inv[dfncnt] = u; W[u] = A[u];
    for (int v : G[u]) if (v != f) {
        DFS1(v, u); if (sz[v] > sz[hson[u]]) hson[u] = v;
        R[u] = R[v]; sz[u] += sz[v]; 
        Ans[u] = (Ans[u] + Ans[v] + 1ull * W[u] * W[v]) % MOD;
        W[u] = (W[u] + W[v]) % MOD;
    } return ;
}
void add(int u, uint k) {
    for (int d : D[u]) {
        cur = (cur + 1ull * mu[d] * sum[d] % MOD * k % MOD) % MOD;
        sum[d] = (sum[d] + k) % MOD; 
    } return ;
}
void del(int u, uint k) {
    for (int d : D[u]) {
        sum[d] = (sum[d] + MOD - k) % MOD; 
        cur = (cur + 1ull * mu[d] * sum[d] % MOD * (MOD - k) % MOD) % MOD;
    } return ;
}
void DFS2(int u, int f, bool kp) {
    for (int v : G[u]) if (v != f && v != hson[u]) DFS2(v, u, false);
    if (hson[u]) { DFS2(hson[u], u, true); }
    for (int v : G[u]) if (v != f && v != hson[u]) 
        for (int i = dfn[v]; i <= R[v]; i ++) add(A[inv[i]], A[inv[i]]);
    add(A[u], A[u]); Ans[u] = (Ans[u] + MOD - cur) % MOD;
    if (!kp) for (int i = dfn[u]; i <= R[u]; i ++) del(A[inv[i]], A[inv[i]]);
}

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int read() {
    int x = 0; char c = getchar();
    for (; !isdigit(c); c = getchar());
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x;
}
void write(int x) {
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

int main() {
    freopen(".in", "r", stdin); freopen(".ans", "w", stdout); 
    n = read(); Sieve();
    for (int i = 1; i <= n; i ++) A[i] = read(), vis[A[i]] = 1;
    for (int i = 1, u, v; i < n; i ++) {
        u = read(), v = read(); G[u].push_back(v); G[v].push_back(u);
    }
    for (int i = 1; i <= m; i ++) if (mu[i] != 0)
        for (int j = i; j <= m; j += i) if (vis[j]) cnt[j] ++;
    for (int i = 1; i <= m; i ++) if (vis[i]) D[i].resize(cnt[i]), cnt[i] = 0;
    for (int i = 1; i <= m; i ++) if (mu[i] != 0)
        for (int j = i; j <= m; j += i) if (vis[j]) D[j][cnt[j] ++] = i;
    DFS1(1, 0); DFS2(1, 0, true);
    for (int i = 1; i <= n; i ++)
        for (int j : G[inv[i]]) if (dfn[j] > i) Ans[inv[i]] = (Ans[inv[i]] + MOD - Ans[j]) % MOD;
    for (int i = 1; i <= n; i ++) write(Ans[i]), putchar('\n');
    return 0;
}