题解 CF809E 【Surprise me!】

Sol1 · 2022-06-25 21:20:03 · 个人记录

怎么题解区一大片虚树，给个不用虚树的做法。

按照套路拆贡献干掉 dis，对于每一个点 u，设其子树里面的点组成的点集为 S_u，于是答案可以写成：

\dfrac{2}{n(n-1)}\sum_{u=1}^n\sum_{x\in S_u}\sum_{y\notin S_u}\varphi(a_xa_y)

设

F(S)=\sum_{x\in S}\sum_{y\notin S}\varphi(a_xa_y)

则我们希望对于所有 u 求出 F(S_u)。

考虑启发式合并。问题可以转化为如下形式：对于两个不交点集 S,T，已知 F(S),F(T)，希望在 O(\min\{S,T\}\operatorname{poly}\log n) 的时间内求得 F(S\cup T)。首先这个 F(S\cup T) 的求和形式里面带一个 \sum_{y\notin S\cup T}，这个对于启发式合并显然很难受。尝试利用 F(S) 和 F(T) 消去之：

&F(S)+F(T)\\ =\ &\sum_{x\in S}\sum_{y\notin S}\varphi(a_xa_y)+\sum_{x\in T}\sum_{y\notin T}\varphi(a_xa_y)\\ =\ &\left(\sum_{x\in S}\sum_{y\in T}\varphi(a_xa_y)+\sum_{x\in S}\sum_{y\notin S\cup T}\varphi(a_xa_y)\right)+\left(\sum_{x\in T}\sum_{y\in S}\varphi(a_xa_y)+\sum_{x\in T}\sum_{y\notin S\cup T}\varphi(a_xa_y)\right)\\ =\ &2\sum_{x\in S}\sum_{y\in T}\varphi(a_xa_y)+\sum_{x\in S}\sum_{y\notin S\cup T}\varphi(a_xa_y)+\sum_{x\in T}\sum_{y\notin S\cup T}\varphi(a_xa_y)\\ =\ &2\sum_{x\in S}\sum_{y\in T}\varphi(a_xa_y)+\sum_{x\in S\cup T}\sum_{y\notin S\cup T}\varphi(a_xa_y)\\ =\ &2\sum_{x\in S}\sum_{y\in T}\varphi(a_xa_y)+F(S\cup T) \end{aligned}

这样问题就转化为求：

\sum_{x\in S}\sum_{y\in T}\varphi(a_xa_y)

这个形式对于启发式合并就友好很多了。不妨设 |S|>|T|，考虑逐步加点，那么可以被进一步简化为对于给定 k 求：

\sum_{x\in S}\varphi(ka_x)

设 c_i 表示 S 中是否存在一个 x 使得 a_x=i，存在为 1，不存在为 0。

\sum_{i=1}^n\varphi(ki)c_i

这看起来就是一个很标准的数论推式子题了。尝试计算这个东西。

&\sum_{i=1}^n\varphi(ki)c_i\\ =\ &\sum_{i=1}^n\dfrac{\varphi(k)\varphi(i)\gcd(k,i)}{\varphi(\gcd(k,i))}c_i\\ =\ &\varphi(k)\sum_{i=1}^n\varphi(i)\cdot\dfrac{\gcd(k,i)}{\varphi(\gcd(k,i))}\cdot c_i\\ =\ &\varphi(k)\sum_{d|k}\dfrac{d}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(di)\left[i\perp\dfrac{k}{d}\right]c_{di}\\ =\ &\varphi(k)\sum_{d|k}\dfrac{d^2}{\varphi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(i)c_{di}\sum_{dt|k,t|i}\mu(t)\\ =\ &\varphi(k)\sum_{d|k}\dfrac{d^2}{\varphi(d)}\sum_{dt|k}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\varphi(ti)c_{dti}\\ =\ &\varphi(k)\sum_{d|k}\dfrac{d^2}{\varphi(d)}\sum_{dt|k}t\mu(t)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\varphi(i)c_{dti}\\ =\ &\varphi(k)\sum_{p|k}\left(\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i)c_{pi}\right)\cdot p\sum_{d|p}\dfrac{d}{\varphi(d)}\mu\left(\dfrac{p}{d}\right)\\ =\ &\varphi(k)\sum_{p|k}\left(\sum_{p|i}\varphi(i)c_{i}\right)\cdot \sum_{d|p}\dfrac{d}{\varphi(d)}\mu\left(\dfrac{p}{d}\right) \end{aligned}

设：

G(n)=\sum_{d|n}\dfrac{d}{\varphi(d)}\mu\left(\dfrac{n}{d}\right)

显然 G(n) 可以 O(n\log n) 预处理。然后只要快速维护 \varphi(i)c_i 的 Dirichlet 后缀和即可 O(d(k)) 计算上式。考虑到这是启发式合并，于是一个元素最多被合并 \log n 次，从而复杂度均摊下来就是 O(\sum d(k)\log n)=O(n\log^2n)。

那么如何快速维护 \varphi(i)c_i 的 Dirichlet 后缀和？考虑使用轻重链剖分实现的树上启发式合并。具体来说，在全局维护一个数组保存 \varphi(i)c_i 的 Dirichlet 后缀和，然后执行如下流程：

先对整个树轻重链剖分。
在树上 DFS，先 DFS 轻儿子，然后扫一遍轻儿子的所有孩子，撤销其对后缀和的影响（即，清空）。
最后 DFS 重儿子，继承其 Dirichlet 后缀和数组。
按照上面的式子进行合并。
暴力用轻儿子的子树里面的点更新 Dirichlet 后缀和数组，即直接往所有约数上面加。这样做，复杂度沿用上面的分析，是 O(n\log^2n)。

这样即可做到实时维护 Dirichlet 后缀和，那么就可以直接按照上面的式子进行合并。然后这题就做完了。总复杂度 O(n\log^2n)。

放个核心代码。

// calc sum_{i=1...n}phi(ki)*c[i]
inline long long Sum(long long k, long long *cds) {
    long long ans = 0;
    for (int x : d[k]) ans = (ans + fv[x] * cds[x]) % mod;
    return ans * phi[k] % mod;
}

inline void Prefix() {
    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j += i) d[j].push_back(i);
    }
    for (int i = 1;i <= n;i++) {
        int tmp = i;
        for (int j = 2;j * j <= tmp;j++) {
            if (tmp % j == 0) {
                p[i].push_back(j);
                while (tmp % j == 0) tmp /= j;
            }
        }
        if (tmp > 1) p[i].push_back(tmp);
    }
    phi[1] = 1; mu[1] = 1;
    for (int i = 2;i <= n;i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            pri[++pcnt] = i;
            mu[i] = -1;
        }
        for (int j = 1;j <= pcnt && i * pri[j] <= n;j++) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                mu[i * pri[j]] = 0;
                break;
            }
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            mu[i * pri[j]] = -mu[i];
        }
    }
    for (int i = 1;i <= n;i++) piv[i] = Power(phi[i], mod - 2);
    for (int i = 1;i <= n;i++) {
        for (int x : d[i]) {
            fv[i] = (fv[i] + mu[i / x] * x * piv[x] % mod + mod) % mod;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int x : d[i]) cnt[x] = (cnt[x] + phi[i]) % mod;
    }
    for (int i = 1;i <= n;i++) dp[i] = (Sum(a[i], cnt) - a[i] * phi[a[i]] % mod + mod) % mod;
    memset(cnt, 0, sizeof(cnt));
}

inline void Dfs1(int u, int fa) {
    siz[u] = 1;
    for (int i = hd[u];~i;i = e[i].nxt) {
        if (e[i].to != fa) {
            Dfs1(e[i].to, u);
            siz[u] += siz[e[i].to];
            if (siz[son[u]] < siz[e[i].to]) son[u] = e[i].to;
        }
    }
}

inline void Dfs2(int u, int fa) {
    v[u].push_back(a[u]);
    for (int i = hd[u];~i;i = e[i].nxt) {
        if (e[i].to != fa && e[i].to != son[u]) {
            Dfs2(e[i].to, u);
            for (int x : v[e[i].to]) {
                v[u].push_back(x);
                for (int y : d[x]) cnt[y] = 0;
            }
            if (v[e[i].to].size() > v[u].size()) swap(v[u], v[e[i].to]);
        }
    }
    if (son[u]) {
        Dfs2(son[u], u);
        swap(v[u], v[son[u]]);
        for (int x : v[son[u]]) v[u].push_back(x);
        v[son[u]].clear(); 
        long long tmp = Sum(a[u], cnt);
        dp[u] = (dp[u] + dp[son[u]] - 2 * tmp + 2 * mod) % mod;
    }
    for (int x : d[a[u]]) cnt[x] = (cnt[x] + phi[a[u]]) % mod;
    for (int i = hd[u];~i;i = e[i].nxt) {
        if (e[i].to != fa && e[i].to != son[u]) {
            long long sum = 0;
            for (int x : v[e[i].to]) sum = (sum + Sum(x, cnt)) % mod;
            dp[u] = (dp[u] + dp[e[i].to] - 2 * sum + 2 * mod) % mod;
            for (int x : v[e[i].to]) {
                for (int y : d[x]) cnt[y] = (cnt[y] + phi[x]) % mod;
            }
            v[e[i].to].clear();
        }
    }
    if (fa >= 0) ans = (ans + dp[u]) % mod;
}