ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

CF1292D Chaotic V. 题解

posted on 2021-01-28 09:27:21 | under 题解 |

来一发虚树题解。

昨天上午开了一场VP,然后机房神仙秒了这个D。我一看这不是虚树题吗?但是我不会写虚树,所以学了一下午,今天来写个题解。

这是一道很好的虚树练手题,至少它让我对虚树有了更深刻的认识。

在进入正题——建虚树之前,我相信大家都能看出来,不同的点数其实不超过5000,所以我们可以打表预处理每个阶乘的唯一分解形式。

然后,如果我们建出了虚树,就把原问题转化成了一个点边均带权的重心问题。接下来还要考虑这个带权重心可能在虚树的点上,虚树的边上,甚至虚树的外面——而后两种是不好处理的。

显然,在虚树的外面肯定不优,接下来我们用调整法证明在虚树的边上不会比在这条边的某个端点上更优。如果这条边两边所有点的权重之和相同,那么我们随便取一个端点,得到的带权路径长度和是一样的;如果两边权重和不同,我们取权重较小一边的端点,一定比这个边上的点更优。实际上,如果一棵虚树的一条边代表原树的一条链,而这条链上全是0权点,那么在这条链之外一定还存在带权重心。

考虑如果要建虚树,我们需要搞定以下几个操作 :

1.给点排序

发现其实不用给点排序。如果我们按除去的那个质因子从小到大的顺序遍历儿子的话,我们发现走上来是砍去最小质因子的过程,而走下去则是乘上最大质因子的过程。所以,既然阶乘的各质因子次数都是单调递增的,dfs序也是单调递增的。

2.求LCA

考虑一个点走到它的各级祖先时砍质因子的过程。发现如果$u$是$v$的祖先,那么$u$前面有若干0,然后接下来一个质因子的次数比$v$小,剩下的质因子次数都和$v$相同。

所以我们要求$l=\operatorname{LCA}(u,v)$,就先求出$u,v$的最长公共后缀,然后接下来一位取$u,v$这一位上的$\min$,剩下的位取$0$。举个例子,比如我们要求$\operatorname{LCA}(15,20)$(可以看看样例的图,括号里表示唯一分解形式) :

$$ \begin{aligned} 15&=(0,1,1,0,...)\\ 20&=(2,0,1,0,...)\\ \operatorname{LCA}(15,20)=5&=(0,0,1,0,...)\\ \end{aligned} $$

3.判断相等

废话。

4.判断祖先关系

其实在第二部分已经讨论过了。我们要判断$u$是不是$v$的后代,只要看$v$第一个非$0$位是不是小于$u$对应位的值,然后后面的位是不是相等。

解决了这几个问题,我们就可以成功地建立虚树。接下来的任务是求出带权重心,我们可以使用换根dp来搞定。

复杂度,预处理是$O(k\log\log k)$,建立虚树是$O(\frac{k^2}{\log k})$,dp是$O(k)$,所以总复杂度$O(\frac{k^2}{\log k})$,速度还可以。

我码力不太行,写了160行才写完。注意一下$k$可能为0,需要特判$0!=1$。

#include<stdio.h>
#include<string.h>

int n;
int b[5002],prime[700],pcnt;
int temp[5002],val[20002];
int cnt;
long long ans=0x7fffffffffffffff;

struct Num
{
    int e[700];
    Num(){ memset(e,0,sizeof(e)); }
    inline bool operator == (Num x)
    {
        for(int i=1;i<=pcnt;i++)
            if(e[i]!=x.e[i]) return 0;
        return 1;
    }
    inline bool operator < (Num x)
    {
        for(int i=1;i<=pcnt;i++)
            if(e[i]!=x.e[i])
                if(e[i]<x.e[i]) return 1;
                else return 0;
        return 0;
    }
}a[20000];

inline void init()
{
    for(int i=2;i<=5000;i++)
        if(!b[i])
        {
            prime[++pcnt]=i;
            for(int j=2*i;j<=5000;j+=i)
                b[j]=1;
        }

    for(int i=1;i<=5000;i++) temp[i]=i;
    for(int i=1;i<=pcnt;i++)
        for(int j=1;j<=5000;j++)
            while(temp[j]%prime[i]==0)
                temp[j]/=prime[i],a[j].e[i]++;
    for(int i=1;i<=5000;i++)
        for(int j=1;j<=pcnt;j++)
            a[i].e[j]+=a[i-1].e[j];
    cnt=5000;
}

struct Edge
{
    int v,w,next;
}e[100002];

int h[50002];
int ecnt;

inline void add_edge(int u,int v,int w)
{
    e[++ecnt]={v,w,h[u]};
    h[u]=ecnt;
    e[++ecnt]={u,w,h[v]};
    h[v]=ecnt;
}

#define min(x,y) ((x)<(y)?(x):(y))

inline Num lca(Num a,Num b)
{
    Num c;
    int i=pcnt;
    for(;a.e[i]==b.e[i];i--) c.e[i]=a.e[i];
    c.e[i]=min(a.e[i],b.e[i]);
    i--;
    for(;i>0;i--) c.e[i]=0;
    return c;
}

inline int dist(Num u,Num v)//jump from u to v
{
    int res=0;
    for(int i=1;i<=pcnt;i++)
        res+=u.e[i]-v.e[i];
    return res;
}

inline bool is_son(Num u,Num v)//check if u is v's son
{
    int i=1;
    for(;i<=pcnt&&!v.e[i];i++);
    if(i>pcnt) return 1;
    if(v.e[i]>u.e[i]) return 0;
    i++;
    for(;i<=pcnt;i++)
        if(v.e[i]!=u.e[i]) return 0;
    return 1;
}

int s[20002],top;

inline void insert(int u)
{
    a[++cnt]=lca(a[s[top]],a[u]);
    if(!(a[cnt]==a[s[top]]))
    {
        while(is_son(a[s[top-1]],a[cnt])&&!(a[s[top-1]]==a[cnt]))
            add_edge(s[top],s[top-1],dist(a[s[top]],a[s[top-1]])),top--;
        if(!(a[cnt]==a[s[top-1]]))
            add_edge(s[top],cnt,dist(a[s[top]],a[cnt])),s[top]=cnt;
        else
            add_edge(s[top],s[top-1],dist(a[s[top]],a[s[top-1]])),top--;
    }
    s[++top]=u;
}

inline void build()
{
    s[++top]=1;
    for(int i=2;i<=5000;i++)
        if(val[i])
            insert(i);
    for(int i=1;i<top;i++)
        add_edge(s[i],s[i+1],dist(a[s[i+1]],a[s[i]]));
}

bool vis[20002];
int sum[20002];
long long dp[20002],f[20002];

void dfs1(int u,int fa)
{
    vis[u]=1;
    sum[u]=val[u];
    f[u]=0;
    for(int i=h[u];i;i=e[i].next)
        if(e[i].v!=fa)
            dfs1(e[i].v,u),sum[u]+=sum[e[i].v],f[u]+=(long long)e[i].w*sum[e[i].v]+f[e[i].v];
}

void dfs2(int u,int fa)
{
    for(int i=h[u];i;i=e[i].next)
        if(e[i].v!=fa)
            dp[e[i].v]=(dp[u]-(f[e[i].v]+(long long)e[i].w*sum[e[i].v])+(long long)e[i].w*(sum[1]-sum[e[i].v])+f[e[i].v]),
            dfs2(e[i].v,u);
}

int main()
{
    scanf("%d",&n);
    for(int i=1,k;i<=n;i++)
        scanf("%d",&k),k==0?val[1]++:val[k]++;
    init();
    build();
    dfs1(1,0);
    dp[1]=f[1];
    dfs2(1,0);
    for(int i=1;i<=cnt;i++)
        if(vis[i]) ans=min(ans,dp[i]);
    printf("%I64d",ans);
    return 0;
}