自动搬运

查看原文

来自洛谷，原作者为

	Tomle bzd

搬运于2025-08-24 23:01:28，当前版本为作者最后更新于2025-08-18 15:53:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

真是紫题吗 /yun，写吐了。

我们记 $S(u,d)$ 表示 $u$ 子树内编号为 $d$ 的倍数的点集。

化式子

$$\begin{aligned} ans_u&=\sum_{d=1}^nb_d\sum_{S'\subset S(u,d)}[\gcd\{S'\}=d\land k\mid\max_{x\in S'}\{a_x\}] \\&=\sum_{T=1}^n(\sum_{d\mid T}b_d\mu(\frac Td))\sum_{S'\subset S(u,T)}[k\mid\max_{x\in S'}\{a_x\}] \end{aligned} $$

$\sum_{d\mid T}b_d\mu(\frac Td)$ 可在 $O(n\ln n)$ 或 $O(n\ln\ln n)$ 的时间复杂度内计算。

对于每个 $T$ 枚举所有编号为 $T$ 倍数的点集 $S_{all}$，显然对于所有 $u$ 有 $S(u,T)\subset S_{all}$。

我们可以对 $S_{all}$ 的所有点建虚树，接下来需要解决 $k\mid\max\{a\}$ 的限制。

假如我们能够得到 $u$ 子树内所有点的点权，我们可以对点权建权值线段树，然后在线段树上维护区间包含多少点权，以及区间内选点使最大值为 $k$ 倍数的方案数。pushup 是容易的。

然后在虚树上线段树合并即可。统计答案树上差分即可。

复杂度？每种 $T$ 的 $S_{all}$ 大小之和是 $O(n\ln n)$，加上线段树合并是 $O(n\ln n\log n)$。

史：

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

const int N = 100005;
// const int V = ;
const int mod = 998244353;
typedef unsigned us;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpi;
typedef vector <ll> vl;
template <class T> using pq = priority_queue <T>;
template <class T> using pqg = priority_queue <T, vector <T>, greater <T> >;

#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repr(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define perr(i, a, b) for (int i = (a); i > (b); --i)

#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back

template <class T1, class T2> inline void ckmn(T1 &a, T2 b) { (a > b) && (a = b, 0); }
template <class T1, class T2> inline void ckmx(T1 &a, T2 b) { (a < b) && (a = b, 0); }

namespace IO {
    // char buf[1 << 23], *p1 = buf, *p2 = buf;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
    template <class T> void rd(T &a, unsigned c = 0) {
        while (c = getchar(), c < 48 || c > 57);
        for (a = 0; c >= 48 && c <= 57; c = getchar()) a = (a << 3) + (a << 1) + (c ^ 48);
    }
    template <class T> void wrt(T x) { if (x > 9) wrt(x / 10); putchar(x % 10 ^ 48); }
} using IO::rd; using IO::wrt;

int n, k, u, v;
int a[N], b[N];
vi T[N], vT[N];
int dep[N], anc[N][20], dfn[N], ind;
int ans[N];
int mk[N];
int A[N], B[N];
int p[N], pc, np[N], mu[N];
int pw2[N];

struct Seg {
    int ls, rs, cnt, dat;
    #define ls(p) tr[p].ls
    #define rs(p) tr[p].rs
    #define cnt(p) tr[p].cnt
    #define dat(p) tr[p].dat
} tr[N << 5];
#define M (L + R >> 1)
int stot;
inline int Nw() { stot++, ls(stot) = rs(stot) = cnt(stot) = dat(stot) = 0; return stot; }

void sieve() {
    mu[1] = 1;
    rep(i, 2, 1e5) {
        if (!np[i]) p[++pc] = i, mu[i] = mod - 1;
        for (int j = 1; i * p[j] <= 1e5; j++) {
            np[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = mu[i] ? mod - mu[i] : 0;
            else break;
        }
    }
}
void dfs1(int u, int fa) {
    dep[u] = dep[fa] + 1, anc[u][0] = fa, dfn[u] = ++ind;
    for (auto v : T[u]) if (v != fa) dfs1(v, u);
}
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    per(i, 18, 0) if (dep[anc[u][i]] >= dep[v]) u = anc[u][i];
    if (u == v) return u;
    per(i, 18, 0) if (anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
    return anc[u][0];
}
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
int make_vtree(int len) {
    sort(A + 1, A + len + 1, cmp);
    int len2 = 0;
    repr(i, 1, len) {
        B[++len2] = A[i];
        B[++len2] = lca(A[i], A[i + 1]);
    }
    B[++len2] = A[len];
    sort(B + 1, B + len2 + 1, cmp);
    len2 = unique(B + 1, B + len2 + 1) - B - 1;
    rep(i, 1, len2) vT[B[i]].clear();
    repr(i, 1, len2) {
        int lc = lca(B[i], B[i + 1]);
        // cout << B[i] << "  " << B[i + 1] << "  " << lc  << endl;
        vT[lc].pb(B[i + 1]);
    }
    return B[1];
}
inline void pushup(int p) {
    dat(p) = (dat(ls(p)) + 1ll * pw2[cnt(ls(p))] * dat(rs(p))) % mod;
    cnt(p) = cnt(ls(p)) + cnt(rs(p));
}
void ins(int p, int x, int L, int R) {
    if (L == R) {
        cnt(p)++;
        if (x % k == 0) dat(p) = (pw2[cnt(p)] - 1 + mod) % mod;
        else dat(p) = 0;
        return;
    }
    if (x <= M) {
        if (!ls(p)) ls(p) = Nw();
        ins(ls(p), x, L, M);
    } else {
        if (!rs(p)) rs(p) = Nw();
        ins(rs(p), x, M + 1, R);
    }
    pushup(p);
}
int merge(int u, int v, int L, int R) {
    if (!u || !v) return u | v;
    if (L == R) {
        cnt(u) += cnt(v);
        if (L % k == 0) dat(u) = (pw2[cnt(u)] - 1 + mod) % mod;
        else dat(u) = 0;
        return u;
    }
    ls(u) = merge(ls(u), ls(v), L, M);
    rs(u) = merge(rs(u), rs(v), M + 1, R);
    pushup(u);
    return u;
}
// void out(int p, int L, int R) {
//     if (!p) return;
//     cout << p << " "  << L << " " << R << " " << cnt(p) << " " << dat(p) << endl;
//     out(ls(p), L, M), out(rs(p), M + 1, R);
// }
int dfs2(int u, int fa, int ca) {
    int rt = Nw();
    if (mk[u]) ins(rt, a[u], 1, n);
    for (auto v : vT[u]) {
        int x = dfs2(v, u, ca);
        rt = merge(rt, x, 1, n);
    }
    int e = 1ll * dat(rt) * ca % mod;
    // cout << u << "  " << fa << "  " << ca << "  " << e << "  " << mk[u] << endl;
    ans[u] = (ans[u] + e) % mod;
    ans[fa] = (ans[fa] - e + mod) % mod;
    // puts("tree:");
    // out(rt, 1, n);
    return rt;
}
void dfs3(int u, int fa) {
    for (auto v : T[u]) {
        if (v == fa) continue;
        dfs3(v, u);
        ans[u] = (ans[u] + ans[v]) % mod;
    }
}
void solve() {
    rd(n), rd(k);
    repr(i, 1, n) {
        rd(u), rd(v);
        T[u].pb(v), T[v].pb(u);
    }
    rep(i, 1, n) rd(a[i]);
    rep(i, 1, n) rd(b[i]);
    sieve();
    rep(i, 1, n) {
        for (int j = 1; i * j <= n; j++) {
            A[i * j] = (A[i * j] + 1ll * mu[i] * b[j]) % mod;
        }
    }
    swap(b, A);
    dfs1(1, 0);
    rep(j, 1, 18) {
        rep(i, 1, n) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
    rep(i, pw2[0] = 1, n) pw2[i] = 2 * pw2[i - 1] % mod;
    rep(i, 1, n) {
        // cout << i << endl;
        int tot = 0;
        for (int j = i; j <= n; j += i) A[++tot] = j, mk[j] = 1;
        int rt = make_vtree(tot);
        stot = 0;
        dfs2(rt, 0, b[i]);
        for (int j = i; j <= n; j += i) mk[j] = 0;
    }
    dfs3(1, 0);
    rep(i, 1, n) wrt(ans[i]), putchar(32);
}
int main() {
    int T = 1;
    if (0) rd(T);
    while (T--) solve();
}