2020牛客暑期多校训练营（第一场）B、Infinite Tree （虚树+思维）

题目链接

题面：

题意：
给定一个无穷的树，对于所有 n > 1 的正整数，n 向 n / mindiv(n) 连边。
其中 mindiv(n) 指的是 n 的最小质因子。
给定m个数 wi ，求 min ${\sum }_{i=1}^m{w}_i\ast dis(u,i!)$i=1∑m​wi​∗dis(u,i!) 。

分析：
（一）
通过移动分析，我么可以得到，最终的 u 一定可以在某个 $i!$i! 处取得最优值。
假设我们现在 root=1，u=1，我们令ans=min ${\sum }_{i=1}^m{w}_i\ast dis(1,i!)$i=1∑m​wi​∗dis(1,i!)
另外我们设 $f\left[x\right]=w\left[x\right]+\sum _{y\in sonx}f\left[y\right]$f[x]=w[x]+y∈sonx∑​f[y]。
现在我们分析，u 从 x 变为 y 的过程。
有 $f\left[1\right]-f\left[y\right]$f[1]−f[y]会多加一段 $dis(x,y)$dis(x,y)， $f\left[y\right]$f[y]会少移动一段 $dis(x,y)$dis(x,y)

那么最终答案就会变化:
$ans=ans+\left(f\right[1]-f[y\left]\right)\ast dis(x,y)-f\left[y\right]\ast dis(x,y)$ans=ans+(f[1]−f[y])∗dis(x,y)−f[y]∗dis(x,y)
$ans=ans+\left(f\right[1]-2\ast f[y\left]\right)\ast dis(x,y)$ans=ans+(f[1]−2∗f[y])∗dis(x,y)

所以如果能得出这棵树来，那么我们可以在O（n）时间内得到答案。

（二）
因为 m 的数量级是 1e5， 如果构造这棵树出来，那么它的节点数是非常多的，所以并不能直接构造这棵树出来。
我们发现，除了这 m 个 i！的节点，其余节点对答案是没有贡献的（即我们的最优值一定会在这m个节点取到）。考虑拉一棵虚树出来。

可是要怎么拉出这棵虚树来呢？

观察此图我们可以发现。
（1）根节点 1 到节点 i！的路径上的质因子大小不增（递减）。
（2）我们唯一分解 $i!=p_1^{e_1}{p}_1^{e_2}...p_k^{e_k}$i!=p1e1​​p1e2​​...pkek​​ 的形式，那么 $dis(1,i!)={\sum }_{i=1}^k{e}_i$dis(1,i!)=i=1∑k​ei​
（3）我们设 i 点的深度为 $d\left[i\right]$d[i]，那么考虑第 i+1 点的深度 $d[i+1]=d\left[i\right]+(i+1)质因子个数$d[i+1]=d[i]+(i+1)质因子个数

（4）若按照上图形式构建这棵树，那么节点 $i!$i! 的dfs序已是递增的。

（5）考虑怎么求 $i!$i! 和 $(i+1)!$(i+1)! 两点的lca：（这些lca一定都为关键节点）
假设 maxdiv(x) 为x的最大质因子，那么 $(i+1)!$(i+1)! 与 $i!$i! 的 lca 一定是 $i!$i! 这条链上最后一条 maxdiv(i+1) 的边对应的节点。
考虑为什么 :
$5!=5^1\ast 3^1\ast 2^3$5!=51∗31∗23
$6!=5^1\ast 3^2\ast 2^4$6!=51∗32∗24
$6!$6! 在除完 $3^1\ast 2^4$31∗24后，与 $5!$5! 除完 $2^3$23后相遇，他们共同的边为 $5^1\ast 3^1$51∗31
所以 $d\left[lca\right]$d[lca]为 $i!$i! 中大于等于 $(i+1)$(i+1)的最大质因子 的质因子个数。

构建虚树的时候我们同样维护一个栈，表示根节点到栈顶元素这条链。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=400100;
const int maxm=100100;
const int up=1000;

int head[maxn],ver[maxn],nt[maxn],tot=1;
int d[maxn],w[maxn],f[maxn],n;
int prime[maxn],ha[maxn],cnt=0;
int c[maxn];
int st[maxn],top;
ll dp[maxn],ans=0,minn;

void Prime(void)
{
    ha[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
            prime[++cnt]=ha[i]=i;
        for(int j=1;j<=cnt&&prime[j]*i<maxn;j++)
        {
            ha[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}

void init(int n)
{
    ans=0,minn=lnf;
    d[1]=tot=1;
    for(int i=0;i<=n;i++)
        c[i]=head[i]=0;
}

void add(int x)
{
    for(;x<=n;x+=(x&(-x)))
        c[x]+=1;
}

int ask(int x)
{
    int ans=0;
    for(;x;x-=(x&(-x)))
        ans+=c[x];
    return ans;
}

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,nt[tot]=head[y],head[y]=tot;
}

void build(void)
{
    for(int i=2;i<=n;i++)
    {
        d[i]=d[i-1]+1;
        int x=i;
        for(;x>ha[x];x/=ha[x])
            d[i]++;
        d[i+n]=ask(n)-ask(ha[x]-1)+1;
        for(x=i;x>1;x/=ha[x])
            add(ha[x]);
    }
    st[top=1]=1;
    for(int i=2;i<=n;i++)
    {
        while(top>1&&d[st[top-1]]>=d[i+n])
            add(st[top-1],st[top]),top--;
        if(d[st[top]]!=d[i+n])
            add(st[top],i+n),st[top]=i+n;
        st[++top]=i;
    }
    while(top>1) add(st[top-1],st[top]),top--;

}

void dfs1(int x,int fa)
{
    //多组输入，w没有清零
    ans+=1ll*(x>n?0:w[x])*(d[x]-d[1]);
    if(x<=n) f[x]=w[x];
    else f[x]=0;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        dfs1(y,x);
        f[x]+=f[y];
    }
}

void dfs2(int x,int fa)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        dp[y]=dp[x]+1ll*(f[1]-2*f[y])*(d[y]-d[x]);
        minn=min(minn,dp[y]);
        dfs2(y,x);
    }
}

int main(void)
{
    //freopen("1.in", "r", stdin);
    //freopen("2.out", "w", stdout);

    Prime();
    while(scanf("%d",&n)!=EOF)
    {
        init(n*2+10);
        for(int i=1;i<=n;i++)
            scanf("%d",&w[i]);
        build();
        dfs1(1,0);
        minn=dp[1]=ans;
        dfs2(1,0);
        printf("%lld\n",minn);
    }
    return 0;
}