CF809E Surprise me!

这是道莫比乌斯反演+虚树的好题啊。

传送门

首先我们知道
$$
\phi(i\times j)=\frac{\phi(i)\times \phi(j)\times gcd(i,j)}{\phi(gcd(i,j))}
$$
一般$\phi$里出现乘积的题都要这么化，之后就变成了一个数学题。

不管$\frac{1}{n(n-1)}$，原式就变成了：
$$
\sum_{i=1}^n\sum_{j=1}^n\frac{\varphi(a_i)\times \phi(a_j)\times gcd(a_i,a_j)}{\phi(gcd(a_i,a_j))}\times dist(i,j)
$$

$a_i$在$\phi$里面让人没法推下去，所以令$b_{a_i}=i$，就会得到一个等价的式子，相当于在枚举$a_i$
$$
\sum_{i=1}^n\sum_{j=1}^n\frac{\varphi(i)\times \phi(j)\times gcd(i,j)}{\phi(gcd(i,j))}\times dist(b_i,b_j)
$$

似乎可以反演的样子，先继续枚举gcd：
$$
\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^n\sum_{j=1}^n[(i,j)=d]\phi(i)\phi(j)\times dist(b_i,b_j)
$$
下面是套路，虽然我必须要写，但大家可以跳过到下面的结论
$$
\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}[(i,j)=1]\phi(id)\phi(jd)\times dist(b_{id},b_{jd})
$$

$$
=\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}\phi(id)\phi(jd)\times dist(b_{id},b_{jd})\sum_{k|(i,j)}\mu(k)
$$

$$
=\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/dk}\sum_{j=1}^{n/dk}\phi(idk)\phi(jdk)\times dist(b_{idk},b_{jdk})
$$

令$T=dk$
$$
=\sum_{T=1}^n\sum_{d|T}\frac{d}{\phi(d)}\mu(\frac{T}{d})\sum_{i=1}^{n/T}\sum_{j=1}^{n/T}\phi(iT)\phi(jT)\times dist(b_{iT},b_{jT})
$$
跳过部分就到这里了。

首先令$f(T)=\sum_{d|T}\frac{d}{\phi(d)}\mu(\frac{T}{d})$，这个函数是可以线筛或者，枚举d去埃筛的，我用的是线筛：

当T是质数时，$f(T)=\frac{1}{T-1}$，当T是质数的m次幂(m>1)时，$f(T)=0$

这个可以自己算一下，由于里面有个$\mu$所以只用枚举d=1或d=质数的一次幂 就行了。

看后面这个式子，它其实就是：
$$
\sum_{i=1}[i|T]\sum_{j=1}[j|T]\phi(i)\phi(j)\times dist(b_i,b_j)
$$

我们之前为了方便去掉了$a_i$，加回来的话就是：
$$
\sum_{i=1}[a_i|T]\sum_{j=1}[a_j|T]\phi(a_i)\phi(a_j)\times dist(i,j)
$$
这个东西的求法是对$a_i|T$的点建一棵虚树，一共建n棵虚树，之后去dp或者枚举每一条边计算贡献，由于$a_i$是一个排列，所以n棵虚树的总点数是调和级数$nlogn$的。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mod 1000000007
using namespace std;
struct node{
    int next,to,z;
}w[400001];
int head[200001],stack[200001],size[200001];
int prime[100001],o[200001],phi[200001],num;
int deep[200001],st[400001][18],logg[400001];
int n,sum,ans,a[200001],b[200001],d[200001],m;
int f[200001],low[200001],cnt,top,idx[200001];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}
inline void link(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
    w[cnt].z=deep[y]-deep[x];
}
inline int ksm(int x,int y){
    int num=1;
    while (y){
        if (y&1) num=mul(x,num);
        x=mul(x,x); y>>=1;
    }
    return num;
}
inline int cmp(int x,int y){
    if (deep[x]<deep[y]) return x; return y;
}
inline bool cmp2(int x,int y){return idx[x]<idx[y];}
inline void euler(){
    phi[1]=o[1]=f[1]=1;
    for (int i=2; i<=n; i++){
        if (!o[i]){
            prime[++prime[0]]=i;
            phi[i]=i-1; low[i]=i;
            f[i]=ksm(i-1,mod-2);
        }
        for (int j=1; j<=prime[0]&&i*prime[j]<=n; j++){
            o[i*prime[j]]=1;
            if (i%prime[j]==0){
                low[i*prime[j]]=low[i]*prime[j];
                if (low[i]!=i) f[i*prime[j]]=mul(f[i/low[i]],f[low[i]*prime[j]]);
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
            f[i*prime[j]]=mul(f[i],f[prime[j]]);
            low[i*prime[j]]=prime[j];
        }
    }
//	memset(f,0,sizeof(f));
//	for (int d=1; d<=n; d++)
//		for (int t=d; t<=n; t+=d)
//			f[t]=add(f[t],mul(mul(d,so[phi[d]]),mu[t/d]));
}
void dfs(int x,int fa){
    st[++num][0]=x; idx[x]=num;
    for (int i=head[x]; i; i=w[i].next){
        if (w[i].to!=fa){
            deep[w[i].to]=deep[x]+1;
            dfs(w[i].to,x);
            st[++num][0]=x;
        }
    }
}
inline int lca(int x,int y){
    x=idx[x],y=idx[y];
    if (x>y) swap(x,y);
    int k=logg[y-x+1];
    return cmp(st[x][k],st[y-(1<<k)+1][k]);
}
inline void ins(int x){
    if (x==1) return;
    if (!top){
        stack[++top]=x;
        return;
    }
    int l=lca(stack[top],x);
    while (top&&deep[stack[top-1]]>deep[l])
        link(stack[top-1],stack[top]),top--;
    if (deep[stack[top]]>deep[l]) link(l,stack[top]),top--;
    if (stack[top]!=l) stack[++top]=l;
    stack[++top]=x;
}
void get_pre(int x){
    size[x]=phi[a[x]]*o[x];
    for (int i=head[x]; i; i=w[i].next){
        get_pre(w[i].to);
        size[x]=add(size[x],size[w[i].to]);
    }
    head[x]=0;
}
void debug(){
    for (int x=1; x<=n; x++)
        for (int i=head[x]; i; i=w[i].next)
            printf("%d %d %d\n",x,w[i].to,w[i].z);
}
int main(){
    int x,y;
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
        scanf("%d",&a[i]),b[a[i]]=i;
    for (int i=1; i<n; i++){
        scanf("%d%d",&x,&y);
        link(x,y); link(y,x);
    }
    euler(); dfs(1,0);
    for (int i=2; i<=num; i++) logg[i]=logg[i>>1]+1;
    for (int j=1; j<=logg[num]; j++)
        for (int i=1; i+(1<<(j-1))-1<=num; i++)
            st[i][j]=cmp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    stack[0]=1;
    memset(head,0,sizeof(head));
    memset(o,0,sizeof(o));
    for (int t=1; t<=n; t++){
        if (!f[t]) continue;
        m=cnt=sum=0;
        for (int i=t; i<=n; i+=t) d[++m]=b[i],o[b[i]]=1;
        sort(d+1,d+m+1,cmp2);
        for (int i=1; i<=m; i++) ins(d[i]);
        while (top) link(stack[top-1],stack[top]),top--;
//		printf("%d\n",t); debug();
        get_pre(1);
//		if (a[1]%t) size[1]=dec(size[1],phi[a[1]]);
        for (int i=1; i<=cnt; i++){
            y=w[i].to;
            sum=add(sum,mul(mul(w[i].z,dec(size[1],size[y])),size[y]));
        }
        sum=add(sum,sum);
        ans=add(ans,mul(f[t],sum));
//		printf("%d\n",sum);
        for (int i=1; i<=m; i++) o[d[i]]=0;
    }
    printf("%d\n",mul(mul(ans,ksm(n,mod-2)),ksm(n-1,mod-2)));
    return 0;
}