Codefoces

Luogu

分析

$\mathsf{\color{black}{x}\color{red}{gzc}}$ 讲这题,报警了...

首先要知道

$$ \varphi(ij)=\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} $$

可以暴力拆式子证明。

为了方便,设 $p_{a_i}=i$ 。

于是就可以来推一推式子了(推的比较长,如果想看简单的可以去看 xgzc 的):

$$ \begin{aligned} \text{原式}&=\sum_{i=1}^n\sum_{j=1}^n\varphi(ij)dis(p_i,p_j)\\ &=\sum_{i=1}^n\sum_{j=1}^n\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}dis(p_i,p_j)\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]\varphi(i)\varphi(j)dis(p_i,p_j)\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[\gcd(i,j)=1]\varphi(id)\varphi(jd)dis(p_{id},p_{jd})\\ &=\sum_{d=1}^n\frac{d}{\varphi(d)}\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/dk}\sum_{j=1}^{n/dk}\varphi(idk)\varphi(jdk)dis(p_{idk},p_{jdk})\\ &=\sum_{T=1}^n\sum_{d|T}\frac{d}{\varphi(d)}\mu\left(\frac{T}{d}\right)\sum_{i=1}^{n/T}\sum_{j=1}^{n/T}\varphi(iT)\varphi(jT)dis(p_{iT},p_{jT})\\ &=\sum_{T=1}^n\color{red}{\sum_{d|T}\frac{d}{\varphi(d)}\mu\left(\frac{T}{d}\right)}\sum_{T|i}\sum_{T|j}\varphi(i)\varphi(j)dis(p_i,p_j) \end{aligned} $$

红色的部分可以枚举倍数预处理,复杂度调和级数。于是只要现在考虑怎么求

$$ \sum_{T|i}\sum_{T|j}\varphi(i)\varphi(j)dis(p_i,p_j) $$

令 $w_{p_i}=\varphi(i)$ ,那么就相当于要求

$$ \sum_{T|i}\sum_{T|j}w_{p_i}w_{p_j}dis_{p_i,p_j} $$

可以考虑把所有满足 $T|i$ 的 $p_i$ 拿出来建虚树,然后树形 DP 。

设 $dp_u$ 为 $u$ 子树的答案。假设现在要把 $v$ 子树合并到 $u$ 中去(画的似乎有点丑)

那么有

$$ dp_u=dp_u+dp_v+\sum_{i\in U}\sum_{j\in V}w_iw_jdis(i,j) $$

继续推式子:

$$ \begin{aligned} &\sum_{i\in U}\sum_{j\in V}w_iw_jdis(i,j)\\ =&\sum_{i\in U}w_i\sum_{j\in V}w_j(dis(i,u)+l+dis(v,j))\\ =&\left(\sum_{i\in U}w_idis(i,u)\sum_{j\in V}w_j\right)+\left(len\sum_{i\in U}w_i\sum_{j\in V}w_j\right)+\left(\sum_{i\in U}w_i\sum_{j\in V}w_jdis(v,j)\right) \end{aligned} $$

$$ f_u=\sum_{i\in U}w_idis(i,u)\\g_u=\sum_{i\in U}w_i $$

$f$ 和 $g$ 都很好转移,同时 $dp$ 也很好转移了。

因为 DP 只统计了 $i<j$ 的情况,所以要答案要乘 $2$ ;最后答案记得还要乘上 $\frac{1}{n(n-1)}$ 。

其实这题写起来挺休闲的

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int mod=1e9+7;

inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod)
        if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,p[N];
struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dep[N],fa[N],sz[N],hson[N],top[N];
int dfn[N],low[N],tim=0;
inline void dfs1(int u,int f) {
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    dfn[u]=++tim,top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
    low[u]=tim;
}

inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if (dep[u]<dep[v]) swap(u,v);
    return v;
}
inline int getdis(int u,int v) {
    return dep[u]+dep[v]-(dep[getlca(u,v)]<<1);
}

int pri[N],v[N],cnt=0;
int mu[N],phi[N],f[N];
inline void sieve() {
    mu[1]=phi[1]=1;
    for (re int i=2;i<=n;++i) {
        if (!v[i]) pri[++cnt]=i,mu[i]=mod-1,phi[i]=i-1;
        for (re int j=1;j<=cnt&&i*pri[j]<=n;++j) {
            v[i*pri[j]]=1;
            if (i%pri[j]) mu[i*pri[j]]=mod-mu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
            else { phi[i*pri[j]]=phi[i]*pri[j]; break; }
        }
    }
    for (re int d=1;d<=n;++d)
        for (re int i=d;i<=n;i+=d)
            f[i]=(f[i]+1ll*d*qpow(phi[d],mod-2)%mod*mu[i/d]%mod)%mod;
}

namespace VT {
    int w[N];
    struct edge { int v,w,nxt; } e[N<<1];
    int head[N],e_cnt;
    inline void addEdge(int u,int v,int w) {
        e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
    }

    int seq[N<<1],sta[N<<1];
    inline int cmp(int x,int y) { return dfn[x]<dfn[y]; }
    inline void build(int d) {
        e_cnt=0; int tot=0;
        for (re int i=d;i<=n;i+=d) seq[++tot]=p[i],w[p[i]]=phi[i];
        sort(seq+1,seq+tot+1,cmp);
        for (re int i=tot;i>1;--i) seq[++tot]=getlca(seq[i-1],seq[i]);
        seq[++tot]=1;
        sort(seq+1,seq+tot+1,cmp),tot=unique(seq+1,seq+tot+1)-seq-1;
        for (re int i=1,top=0;i<=tot;++i) {
            while (top&&low[sta[top]]<dfn[seq[i]]) --top;
            addEdge(sta[top],seq[i],getdis(sta[top],seq[i]));
            sta[++top]=seq[i];
        }
    }

    int dp[N],f[N],g[N];
    inline void dfs(int u) {
        dp[u]=f[u]=0,g[u]=w[u];
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,l=e[i].w; dfs(v);
            dp[u]=(dp[u]+dp[v]+1ll*f[u]*g[v]+1ll*g[u]*g[v]%mod*l+1ll*g[u]*f[v])%mod;
            f[u]=(f[u]+f[v]+1ll*g[v]*l)%mod,g[u]=(g[u]+g[v])%mod;
        }
        head[u]=w[u]=0;
    }
}

int main() {
    n=read(); sieve();
    for (re int i=1;i<=n;++i) p[read()]=i;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1); int ans=0;
    for (re int i=1;i<=n;++i) {
        VT::build(i),VT::dfs(1);
        ans=(ans+2ll*f[i]*VT::dp[1])%mod;
    }
    printf("%lld\n",1ll*qpow(n,mod-2)*qpow(n-1,mod-2)%mod*ans%mod);
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 54 PM