CF809E Surprise me 题解

大力推式子+莫比乌斯反演+虚树

Statement

给定一棵 \(n\) 个节点的树，每个点有一个权值 \(a[i]\) ，保证 \(a[i]\) 是一个 \(1\dots n\) 的排列。

求 \(\frac{1}{n(n?1)}∑^n_{i=1}∑_{j≠i}φ(a_i\times a_j)\times dist(i,j) \)，对 \(10^9+7\) 取模。

\(n\le 2\times 10^5\)

Solution

据说里面全是套路，但是我啥都第一次

首先忽略 \(\frac 1{n(n-1)}\) ，探究一下 \(\varphi(a_ia_j)\) 咋办

\(\varphi(a_i a_j)=\dfrac {\varphi(a_i)\varphi(a_j)\gcd(a_i,a_j)}{\varphi(\gcd(a_i,a_j))}\)

看到 \(\gcd\) ，直接提出去算；

\[\sum_{d=1}^n \frac d{\varphi(d)}\sum \sum \varphi(a_i)\varphi(a_j)[\gcd(a_i,a_j)==d]dist(i,j) \]

设 \(f(d)=\sum \sum \varphi(a_i)\varphi(a_j)[\gcd(a_i,a_j)==d]dist(i,j)\)

看到 \([n==x]\) 的形式，直接莫反，设

\[F(x)=\sum_{x|d} f(d)=\sum \sum \varphi(a_i)\varphi(a_j)[x|\gcd(a_i,a_j)]dist(i,j) \]

知道 \(f(x)=\sum_{x|d}F(d)\mu(\frac dx)\)，继续算 \(F(x)\)

发现有点拆不动，但其实已经不用拆了，注意到题目中 \(a_i\) 是一个排列，所以 \(x|a_i\) 的只有 \(n\log n\) 个（级数求和）

我们可以考虑直接枚举 \(x\) ，然后把对应的 \(a_i\) 提出来算贡献，也就是算

\[\sum \sum \varphi(a_i)\varphi(a_j)(dep[i]+dep[j]-dep[lca]) \]

把这个式子拆成三个式子，容易发现形如 \(\sum \sum \varphi(a_i)\varphi(a_j) dep[i]\) 的式子可以直接扫一遍得到 $\sum\varphi(a_i)dep[i] $ 和 \(\sum \varphi(a_i)\) 乘起来即可，设这个乘积叫 \(sum\)

考虑咋算 \(res=\sum \sum \varphi(a_i)\varphi(a_j) dep[lca]\)

不妨提一棵虚树出来，然后在虚树上做一个简单树形 DP 即可

那么 \(F(x)=sum\times 2-res\) ，算 \(F\) 是 \(n\log ^2n\) 的，建虚树还有一个 \(log\)

然后 \(O(n\log n)\) 可以反演得到 \(f(x)\)，结束

所以总复杂度 \(O(n\log^2 n)\) ，有一点码量，虚树清零的时候小心

Code

#include
using namespace std;
const int N = 2e5+5;
const int mod = 1e9+7;

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++)
int read(){
    int s=0,w=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}
void inc(int &a,int b){a=a>=mod-b?a-mod+b:a+b;}
void dec(int &a,int b){a=a>=b?a-b:a+mod-b;}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}

int w[N],rev[N],g[N],f[N];
int n,elen,ans;
bool vis[N];

struct Real_Tree{
    vectorEdge[N];
    int siz[N],son[N],top[N],f[N],dep[N],dfn[N];
    int tim;

    void dfs1(int u){
        for(auto v:Edge[u])if(v^f[u])
            dep[v]=dep[f[v]=u]+(siz[v]=1),dfs1(v),siz[u]+=siz[v],
            (siz[v]>siz[son[u]]&&(son[u]=v,1));
    }
    void dfs2(int u,int tp){
        top[u]=tp,dfn[u]=++tim;
        if(son[u])dfs2(son[u],tp);
        for(auto v:Edge[u])if(v^f[u]&&v^son[u])dfs2(v,v);
    }
    int lca(int u,int v){
        while(top[u]^top[v])
            dep[top[u]]