题目：

　　原来以为可以每个质因子分开给答案贡献。

　　大概就是把有这个质因子的数都拿出来建虚树，这样虚树的总点数是 nlogn 的。

　　定义 b[ i ] 表示 i 点原来的权值分解出的 p^t ，其中 p 是目前在做的质因子。那么要求虚树里的 \( \sum\limits_{u} \sum\limits_{v} dis(u,v)*b[u]*b[v] \) 。最后乘 \( \frac{p-1}{p} \) 即可。

　　把 dis( u , v ) 拆成 dep[ u ] + dep[ v ] - 2*dep[ lca ] ，就是每个点贡献 \( dep[cr]*b[cr]*\sum\limits_{i!=cr}b[i] \) ，\( -2*dep[cr]*( (\sum\limits_{i \in tree_cr}b[i])^2 - \sum\limits_{i \in tree_cr}b[i]^2 ) \)

　　还要考虑当前质因子的 “虚树上的点与虚树外的点” 的贡献，就是 \( b[cr]*\sum\limits_{i}dis(i,cr) \) 。要求 “该点与虚树外的点的距离和” ，可以用 “该点与所有点的距离和” - “该点与虚树上点的距离和” ， 换根 DP 一番即可。

　　然后把各种质因子的贡献加起来。

　　试了一下自己造的样例：

4

1 2 3 4

1 2

1 3

3 4

　　发现可以。也没试试题面的样例，就开始写。写完发现是不对的。

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define pb push_backusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}const int N=2e5+5,K=17,mod=1e9+7;int upt(int x){
    while(x>=mod)x-=mod;while(x<0)x+=mod;return x;}int pw(int x,int k){
     int ret=1;while(k){
    if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}int n,a[N],hd[N],xnt,to[N<<1],nxt[N<<1],ans;int tim,dfn[N],dep[N],pre[N][K+5],siz[N],sm[N];int pri[N],mnd[N],cnt,dy[N]; bool vis[N];struct Node{  int v,w;  Node(int v=0,int w=0):v(v),w(w) {}  bool operator< (const Node &b)const  {
     return dfn[(*this).v]
          
           
             vt[N];namespace VT{ Node q[N]; int tot,sta[N],top,ret,p; int a[N],hd[N],xnt,to[N<<1],nxt[N<<1]; int siz[N],s2[N],alsm,vl[N],v2[N]; void add(int x,int y) {to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;} int get_lca(int x,int y) { if(dep[x]
            
             =0;t--) if(dep[pre[x][t]]>=dep[y])x=pre[x][t]; if(x==y)return x; for(int t=K;t>=0;t--) if(pre[x][t]!=pre[y][t]) x=pre[x][t], y=pre[y][t]; return pre[x][0]; } void build() { xnt=alsm=0; sort(q+1,q+tot+1); int st,u=q[1].v; if(u!=1){sta[top=1]=1; a[1]=0; hd[1]=0; st=1;}//hd[]!! else {sta[top=1]=u; a[u]=q[1].w; hd[u]=0; st=2;} for(int i=st;i<=tot;i++) { u=q[i].v; int lca=get_lca(u,sta[top]); a[u]=q[i].w; alsm=upt(alsm+a[u]); while(dfn[sta[top]]>dfn[lca]) { if(dfn[sta[top-1]]>=lca)add(sta[top-1],sta[top]); else add(lca,sta[top]); top--; } if(sta[top]!=lca) { sta[++top]=lca; a[lca]=0; hd[lca]=0;} sta[++top]=u; hd[u]=0; } for(int i=top-1;i;i--)add(sta[i],sta[i+1]); } void dfs(int cr) { if(a[cr]){siz[cr]=1;vl[cr]=a[cr];v2[cr]=(ll)a[cr]*a[cr]%mod;} else siz[cr]=vl[cr]=v2[cr]=0; s2[cr]=0; for(int i=hd[cr],v;i;i=nxt[i]) { dfs(v=to[i]); siz[cr]+=siz[v]; vl[cr]=upt(vl[cr]+vl[v]); v2[cr]=upt(v2[cr]+v2[v]); s2[cr]=(s2[cr]+s2[v]+(ll)siz[v]*(dep[v]-dep[cr]))%mod;//dep } if(a[cr])ret=(ret+(ll)dep[cr]*a[cr]%mod*upt(alsm-a[cr]))%mod; ret=(ret-dep[cr]*((ll)vl[cr]*vl[cr]%mod-v2[cr]))%mod; } void dfsx(int cr) { if(a[cr])ret=(ret+(ll)upt(sm[cr]-s2[cr])*a[cr]*2)%mod; for(int i=hd[cr],v;i;i=nxt[i]) { v=to[i]; int tp=(s2[cr]-s2[v]-(ll)siz[v]*(dep[v]-dep[cr]))%mod; tp=(tp+(ll)(tot-siz[v])*(dep[v]-dep[cr]))%mod;//tot s2[v]=upt(s2[v]+tp); dfsx(v); } } void solve() { build(); dfs(1); ret=upt(ret<<1); dfsx(1);//*2 ret=(ll)ret*(p-1)%mod*pw(p,mod-2)%mod; ans=upt(ans+ret); ret=0;//ret=0 }}void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}void init(){ ll d; for(int i=2;i<=n;i++) { if(!vis[i])pri[++cnt]=i,mnd[i]=i,dy[i]=cnt; for(int j=1;j<=cnt&&(d=(ll)i*pri[j])<=n;j++) { vis[d]=1;mnd[d]=pri[j];if(i%pri[j]==0)break;} }}void dfs(int cr,int fa){ siz[cr]=1; dfn[cr]=++tim; dep[cr]=dep[fa]+1; pre[cr][0]=fa; for(int t=1,d=fa;(d=pre[d][t-1]);t++) pre[cr][t]=d; for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { dfs(v,cr); siz[cr]+=siz[v]; sm[cr]=(upt(sm[cr]+sm[v])+siz[v]); }}void dfsx(int cr,int fa){ for(int i=hd[cr],v;i;i=nxt[i]) if((v=to[i])!=fa) { int tp=upt(sm[cr]-sm[v]-siz[v]); tp=upt(tp+n-siz[v]); sm[v]=upt(sm[v]+tp); dfsx(v,cr); }}int main(){ n=rdn(); init(); for(int i=1;i<=n;i++) { a[i]=rdn(); int k=a[i]; while(k>1) { int tp=1,d=mnd[k]; while(mnd[k]==d)k/=d,tp*=d; vt[dy[d]].pb(Node(i,tp));//dy[] } } for(int i=1,u,v;i
            
           
          
         
        
       
      

　　题解：

　　原来都不太了解这样形式的莫比乌斯反演：

　　　　若 \( f(i)=\sum g(倍数) \) ，则 \( g(i)=\sum f(倍数)*\mu(倍率) \) 

　　一般这里可以用容斥解决。就是从大到小枚举，求出 \( \sum g(倍数) \) ，把多余的 f( ) 减去即可。此时更大的 f( ) 已求出了。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;int rdn(){  int ret=0;bool fx=1;char ch=getchar();  while(ch>'9'||ch<'0'){
    if(ch=='-')fx=0;ch=getchar();}  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();  return fx?ret:-ret;}const int N=2e5+5,K=17,mod=1e9+7;int upt(int x){
    while(x>=mod)x-=mod;while(x<0)x+=mod;return x;}int pw(int x,int k){
     int ret=1;while(k){
    if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}int n,a[N],dy[N],hd[N],xnt,to[N<<1],nxt[N<<1];int tim,dfn[N],dep[N],f[N];int tot,L[N],R[N],q[N<<1],st[N<<1][K+5],lg[N<<1],bin[K+5];int pri[N],phi[N],cnt; bool vis[N];struct Node{  int v,w;  Node(int v=0,int w=0):v(v),w(w) {}  bool operator< (const Node &b)const  {
     return dfn[(*this).v]
         
          L[y]    int l=R[x], r=L[y], d=lg[r-l+1];    if(dfn[st[l][d]]
          
           dfn[lca])      {        if(dfn[sta[top-1]]>=dfn[lca])//dfn[lca] not lca!!          add(sta[top-1],sta[top]);        else {hd[lca]=0;fg=1;add(lca,sta[top]);}//        top--;      }    if(sta[top]!=lca)      { sta[++top]=lca; a[lca]=0; if(!fg)hd[lca]=0;}    sta[++top]=u; hd[u]=0;      }    for(int i=top-1;i;i--)add(sta[i],sta[i+1]);  }  void dfs(int cr)  {    vl[cr]=a[cr]; v2[cr]=(ll)a[cr]*a[cr]%mod;    for(int i=hd[cr],v;i;i=nxt[i])      {    dfs(v=to[i]);    ret=(ret-2ll*dep[cr]*vl[cr]%mod*vl[v])%mod;    vl[cr]=upt(vl[cr]+vl[v]);    v2[cr]=upt(v2[cr]+v2[v]);      }    ret=(ret+(ll)dep[cr]*a[cr]%mod*upt(sm-a[cr]))%mod;  }  void solve()  {    build(); dfs(1); ret=upt(ret<<1);//*2    f[p]=upt(ret); ret=0;//ret=0  }}void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}void init(){  ll d; phi[1]=1;//  for(int i=2;i<=n;i++)    {      if(!vis[i])pri[++cnt]=i,phi[i]=i-1;      for(int j=1;j<=cnt&&(d=(ll)i*pri[j])<=n;j++)    {      vis[d]=1;      if(i%pri[j]==0){phi[d]=(ll)phi[i]*pri[j]%mod;break;}      phi[d]=(ll)phi[i]*phi[pri[j]]%mod;    }    }}void dfs(int cr,int fa){  dfn[cr]=++tim; dep[cr]=dep[fa]+1;  q[++tot]=cr; L[cr]=tot;  for(int i=hd[cr],v;i;i=nxt[i])    if((v=to[i])!=fa) dfs(v,cr),q[++tot]=cr;//every pass!!!  R[cr]=tot;}void lca_ini(){  for(int i=2;i<=tot;i++)lg[i]=lg[i>>1]+1;  bin[0]=1;  for(int i=1;i<=lg[tot];i++)bin[i]=bin[i-1]<<1;  for(int i=1;i<=tot;i++)st[i][0]=q[i];  for(int t=1;t<=lg[tot];t++)    for(int i=1;i+bin[t]-1<=tot;i++)      {    if(dfn[st[i][t-1]]