2020牛客暑期多校训练营（第一场） Infinite Tree

题目描述

样例
输入

3
1 1 1
4
3 1 2 4
4
0 0 0 0

输出

3
17
0

思路
本题需要用到虚树的知识，不会的可以看看我的这篇博客。
然后只要魔改一下模板代码即可，官方题解如下：

简单来说就是要把 $n!$的数字存下来，存的时候只要存它的所有的因子即可。如果用 $sum[i][j]$来表示 $i!$第 $j$因子的个数，其中 $j$表示从 $2$开始的第 $j$个因子，用 $num[i]$存储。
$(n+1)!$比 $n!$只多了一个因子 $n$，所以只要在 $n!$的因子数量上再加上 $n$的因子即可。且拍一拍脑袋我们会知道， $(n+1)!$和 $n!$的 $lca$的深度(最近公共祖先深度，也就是出现分叉的地方的深度)是因子从右往左第一个因子数量出现不同的因子。它的最小值加上比它大的因子数量。例如：
$num$ $2$ $3$ $5$ $7$ $11$ $12$
$sum[2]$ $1$
$sum[3]$ $1$ $1$
$sum[4]$ $3$ $1$
$sum[5]$ $3$ $1$ $1$
$sum[6]$ $4$ $2$ $1$
比如 $6!$和 $5!$，它们因子 $5$的数量相同，因子 $3$的数量不同，所以它们在深度为 $1+1=2$出现分叉。
比如 $6!$和 $4!$，它们因子 $5$的数量不同，所以它们在深度 $1$出现分叉。
根据这个规律，我们可以构建虚树，答案也可以知道了，具体细节可以看一下代码。
代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) x&-x
const int maxn=2e5+5;
struct node{int to,next;}vec[maxn];
int n,cnt,tot,top,a[maxn],b[maxn],c[maxn],d[maxn],e[maxn],h[maxn],l[maxn],r[maxn],dep[maxn],stk[maxn];
ll ans;
void add(int u,int v){vec[++cnt]=(node){v,h[u]};h[u]=cnt;}
int d1(int x){int s=0;for(;x;x-=low(x))s+=c[x];return s;}
void d2(int x,int y){for(;x<=n;x+=low(x))c[x]+=y;}
void p()
{for(int i=2;i<=n;i++){l[i]=l[i-1]+1;int j=i;for(;j!=b[j];j/=b[j])l[i]++;r[i]=d1(n)-d1(j-1);for(j=i;j!=1;j/=b[j])d2(b[j],1);}
}
void dfs1(int x,int f)
{ans+=1ll*a[x]*l[x];for(int i=h[x];i;i=vec[i].next){int son=vec[i].to;if(son!=f)dfs1(son,x),a[x]+=a[son];}
}
void dfs2(int x,int f)
{for(int i=h[x];i;i=vec[i].next){int son=vec[i].to;if(son!=f&&(a[1]-2*a[son])<0)ans+=1ll*(a[1]-2*a[son])*(l[son]-l[x]),dfs2(son,x);}
}
void slove(){for(int i=2;i<=1e5;i++)if(!b[i])for(int j=i;j<=1e5;j+=i)if(!b[j])b[j]=i;}
void q(){for(int i=1;i<=tot;i++)h[i]=a[i]=c[i]=0;cnt=ans=0;}
void build()
{tot=n,top=1;stk[1]=1;for(int i=2;i<=n;i++){while(top>1&&l[stk[top-1]]>=r[i])add(stk[top-1],stk[top]),top--;if(l[stk[top]]!=r[i])l[++tot]=r[i],add(tot,stk[top]),stk[top]=tot;stk[++top]=i;}while(top>1)add(stk[top-1],stk[top]),top--;
}
int main()
{ b[1]=1;slove();while(~scanf("%d",&n)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);p();build();dfs1(1,0);dfs2(1,0);printf("%lld\n",ans);q();}
}