题目大意

定义为n的最小质因子，构造一棵无限的树，树上每个n(n>1)与相连。
定义为到间的边的数量（距离），给出与数组，求出图片说明 。

解题思路

一

本题因为树上节点过多，用虚树来优化树形dp是一种方法。
所以，我们可以虚树二次扫描换根，求解树的带权重心来得到答案。

带权重心介绍：https://baike.baidu.com/item/树的重心/20416316?fr=aladdin
本人关于虚树的博客：https://blog.nowcoder.net/n/721cb2bb714e44e59796e713d3c1420e

二

为什么可以用到虚树呢？

推荐参考，讲解很详细：https://blog.nowcoder.net/n/df889adfaf824d50ad2291f4d2eb04a2
按照他的思路走下去，也是非常易懂的。

简而言之，我们定义
使用上方链接中的图，先来看看这个图(假设所有=1，蓝字标注数值)
图片说明
除了绿色点之外，其它的点的值都与子节点相等。那么如果我们能够移动到点v，就有，如果，那么肯定会继续移动下去。
所以，其它的点都不重要，只需要保留绿色点即可，这就是虚树的思想了。

三

建立虚树，我们还要知道关键点的dfs序的大小关系。

  • 我们先设数，而分解质因数后会是这样的形式：

  • 而我们的，在上面式子的基础上，会增加一些上的的幂次，或者加入新的。
    我们设从右往左第一个幂次不等的质因数为（此非上方的，有点混乱请见谅），则在走完以后，会走，而会继续走，使的dfs序变大。

  • 当(i+1)是一个质数时，显然第一个幂次不等的质因子就是新的。在这种情况下dfs序会更小；
    综上，在递归时，对于任意的，恒成立。

  • 所以，可以得出
    （这里按一般树形dp的定义方式，但是我的丑代码中直接用更方便的a,b,c,d等等替代了）

  • 稍加思索，我们在这里要求的可以表示为(lca,最近公共祖先)，而和的，就是。
    当是一个质数时，他们的为1构建虚树的过程，就是利用栈维护一条链，出现新的，而这个不会再和其它点再求。因此，只需要处理出和的的深度即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int M=200010;
int w[M],c[M],m[M],l[M],b[M],s[M],n,t,tot;
long long ans;
vector<int> v[M];
int lowbit(int x) {return x&-x;}
void add(int x,int y)
{
    v[x].push_back(y);
    v[y].push_back(x);
}
int find(int x)
{
    int y=0;
    while(x) y+=c[x],x-=lowbit(x);
    return y;
}
void build()
{
    tot=n,s[t=1]=1;
    int x,i,j;
    for(i=2;i<=n;i++)
    {
        b[i]=b[i-1]+1;
        for(j=i;j!=m[j];j/=m[j]) b[i]++;
        l[i]=find(n)-find(j-1);
        for(j=i;j!=1;j/=m[j])
        {
            x=m[j];
            while(x<=n)
            {
                c[x]++;
                x+=lowbit(x);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        while(t>1 && b[s[t-1]]>=l[i])
        {
            add(s[t-1],s[t]);
            t--;
        }
        if(b[s[t]]!=l[i])
        {
            b[++tot]=l[i];
            add(tot,s[t]);
            s[t]=tot;
        }
        s[++t]=i;
    }
    while(t>1)
    {
        add(s[t-1],s[t]);
        t--;
    }
}
void dfs(int x,int y)
{
    ans+=1ll*w[x]*b[x];
    int z,i;
    for(i=0;i<v[x].size();i++)
    {
        z=v[x][i];
        if(z!=y)
        {
            dfs(z,x);
            w[x]+=w[z];
        }
    }
}
void ddfs(int x,int y)
{
    int z,i;
    for(i=0;i<v[x].size();i++)
    {
        z=v[x][i];
        if(z!=y && (w[1]-w[z]*2)<0)
        {
            ans+=1ll*(w[1]-w[z]*2)*(b[z]-b[x]);
            ddfs(z,x);
        }
    }
}
int main()
{
    int i,j;
    for(i=2;i<=1e5;i++)
        if(!m[i])
            for(j=i;j<=1e5;j+=i)
                if(!m[j]) m[j]=i;
    while(scanf("%d",&n)!=EOF)
    {
        t=ans=0;
        for(i=1;i<=tot;i++)
        {
            v[i].clear();
            c[i]=w[i]=l[i]=b[i]=0;
        }
        for(i=1;i<=n;i++)
            scanf("%d",&w[i]);
        build();
        dfs(1,0);
        ddfs(1,0);
        printf("%lld\n",ans);
    }
    return 0;
}