Infinite Tree

https://ac.nowcoder.com/acm/contest/5666/B

题意：

题解：

参考博客
看了好一阵子才明白。。。emm。
我们先按照题意画出一部分树
在这里插入图片描述
我们先不考虑复杂度，这题应该怎么做？
题目给了每个点的权值w[i]，问一个点到所有的节点路径长度*点权之和最小是多少，很明显是树形dp
dp[i]表示以i为根的子树到i的w和
sum[i]表示乘上距离之后的答案
dep[i]表示深度，now为当前节点，son为子节点
则有：

dp[now]= w[now]
sum[now]=0
dp[now]+=dp[son]
sum[now]+=sum[son]+(dep[son]-dep[now])*sum[son]

但是以now为根并不一定是最佳答案，所以我们还要不断的换根，求出最佳答案
如果将now为根转移到son为根，我们不用重新算一遍，只需要在之前的基础上

sum[now]-=sum[son]+(dep[son]-dep[now])*dp[son]
dp[now]-=dp[son]
sum[son]+=sum[now]+(dep[son]-dep[now])*dp[now]
dp[son]+=dp[now]

这样就OK了
但是！
题目是要求u到i！的距离，i！的增长速度很快，树的增长也是很快，如果全建出来肯定TLE了，所以我们没办法将整棵树建立，只能选择性建立，这要用到虚树
我们将阶乘点当做关键点，保留关键点及其lca，然后建立数就行
现在又有一个新问题，lca怎么计算？
我们首先考虑a！和(a+1)!的dfn谁大？
因为后者的因子一定包含前者的因子，所以除以mindiv后，（a+1）！的深度肯定更大，所以这些阶乘数的dfn是随a值从小到大的，这样我们只需要考虑相邻两个点的lca即可
我们列一个表格记录阶乘数分解后有多少个质数
在这里插入图片描述
我们根据上面的表格来列出相邻的LCA
2!和3 ! : 1，深度为1
3!和4 ! : 6，深度为3
4!和5 !: 1，深度为1
5!和6 !: 15，深度为3
6!和7 !: 1，深度为1
我们可以得出，对于a！和(a+1)!，LCA就是从大到小公共的质因子的乘积，遇到不同的就停止，深度是相同的个数+1
例如5！和6！：
5！分解后：5 3 2 2 2
6！：5 3 3 2 2 2 2
从大到小，一样的是5和3 ，（从第三位开始不一样，停止）
lca就是15，深度就是3
在这里插入图片描述
可以得到dep[lca((i+1)!,i!)] = sum(maxdiv(i+1),n)
sum(maxidv(i+1),n)为原本i！中大于等于maxdiv(i+1)的因子个数
这样我们就可以快速算出LCA
但是还是不够快，如果对于每个数都扫一次的话，还是很慢。所以，需要一个快速地查找求和，修改的算法，那就是用到了线段树或树状数组

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1ll<<60
using namespace std;
const int MAXN=1e5+10;
int num[MAXN],w[MAXN<<1],d[MAXN<<1],stk[MAXN];
int ldfn[MAXN],rdfn[MAXN],dep[MAXN],lcad[MAXN],m;
int mndv[MAXN],pcnt=0;
ll dp1[MAXN<<1],dp2[MAXN<<1],ans;
vector<int> vir[MAXN<<1];
ll tr[MAXN<<2];//注意开long long
void Build(int root,int l,int r)
{
    tr[root]=0;
    if(l==r) return;
    int mid=l+r>>1;
    Build(root<<1,l,mid);
    Build(root<<1|1,mid+1,r);
}
void Change(int root,int l,int r,int x)
{
    if(l==r){
        tr[root]++;
        return;
    }
    int mid=l+r>>1;
    if(x<=mid) Change(root<<1,l,mid,x);
    else Change(root<<1|1,mid+1,r,x);
    tr[root]=tr[root<<1]+tr[root<<1|1];
}//x是插入的质数，要将其计数+1
int Query(int root,int x,int l,int r)
{              
    if(l>=x) return tr[root];
    int mid=l+r>>1;
    if(x<=mid) return Query(root<<1,x,l,mid)+Query(root<<1|1,x,mid+1,r);
    else if(x>mid) return Query(root<<1|1,x,mid+1,r);
}//查找当前质数的个数
void build()
{//^不等于，相当于!=
    dep[1]=1;
    for(int i=2;i<=m;i++)
    {
        dep[i]=dep[i-1];
        int j=i;
        while(j^mndv[j]) j/=mndv[j];
        lcad[i]=Query(1,j,1,m)+1;
        for(j=i;j^1;dep[i]++,j/=mndv[j]) Change(1,1,m,mndv[j]);
    }
    int top=0,tot=m;stk[++top]=1;
    for(int i=2;i<=m;i++){
        if(top==1||lcad[i]==dep[stk[top]]){
            stk[++top]=i;continue;
        }
        while(top>1&&lcad[i]<=dep[stk[top-1]]){
            vir[stk[top-1]].push_back(stk[top]);
            top--;
        }//建虚树的基本操作，不会的建议去学习一下
        if(lcad[i]^dep[stk[top]]){
            dep[++tot]=lcad[i];
            w[tot]=0;
            vir[tot].push_back(stk[top]);
            stk[top]=tot;
        }
        stk[++top]=i;
    }
    while(top>1){
        vir[stk[top-1]].push_back(stk[top]);
        top--;
    }
}//原理同上，供参考
void dfs1(int x,int fa)
{
    dp1[x]=w[x];
    dp2[x]=0;
    for(int i=0;i<vir[x].size();i++){
        int son=vir[x][i];
        if(son==fa) continue;
        dfs1(son,x);
        dp1[x]+=dp1[son];
        dp2[x]+=dp2[son]+(dep[son]-dep[x])*dp1[son];
    }
}
void dfs2(int x,int fa)
{
    ans=min(ans,dp2[x]);
    for(int i=0;i<vir[x].size();i++){
        int son=vir[x][i];
        if(son==fa) continue;
        ll x1=dp1[x],x2=dp2[x],son1=dp1[son],son2=dp2[son];
        dp2[x]-=dp2[son]+(dep[son]-dep[x])*dp1[son];
        dp1[x]-=dp1[son];
        dp2[son]+=dp2[x]+(dep[son]-dep[x])*dp1[x];
        dp1[son]+=dp1[x];
        dfs2(son,x);
        dp1[x]=x1,dp2[x]=x2,dp1[son]=son1,dp2[son]=son2;
    }
}//树形dp+换根，非重点，且是模板一套的问题，上面已经分析
int main()
{
    mndv[1]=1;
    for(int i=2;i<MAXN;i++)
        if(!mndv[i])
            for(int j=i;j<MAXN;j+=i)
                if(!mndv[j]) mndv[j]=i;//预处理出每个数的mindiv，之后分解时可以用
    while(~scanf("%d",&m)){
        for(int i=1;i<=m;i++)
            scanf("%d",&w[i]);
        for(int i=0;i<=m*2;i++){
            vir[i].clear();
            dp1[i]=dp2[i]=0;
        }
        Build(1,1,m);
        build();
        dfs1(1,0);
        ans=dp2[1];
        dfs2(1,0);
        printf("%lld\n",ans);
    }
}

#include<bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 10;
//建立虚树点数tot < 2n, 空间开两倍

int n, w[MAX];
ll ans;

//树状数组
int c[MAX];
void upd(int p, int k) { for (; p <= n; p += lowbit(p)) c[p] += k; }
int query(int p) { int res = 0; for (; p; p -= lowbit(p)) res += c[p]; return res; }

int mindiv[MAX];
void sieve(int siz) {//筛mindiv
    for (int i = 2; i <= siz; i++)
        if (!mindiv[i])
            for (int j = i; j <= siz; j += i)
                if (!mindiv[j])
                    mindiv[j] = i;
}

int lcadep[MAX], dep[MAX];
int st[MAX], top, tot;//stack, top, tot:虚树点数
vector<int> g[MAX];//虚树
void add_edge(int u, int v) { g[u].push_back(v), g[v].push_back(u); }

void buildVirtualTree() {
    tot = n;
    st[top = 1] = 1;
    for (int i = 2; i <= n; i++) {
        dep[i] = dep[i - 1] + 1; 
        int j = i;
        for (; j != mindiv[j]; j /= mindiv[j]) dep[i]++;
        lcadep[i] = query(n) - query(j - 1);
        for (j = i; j != 1; j /= mindiv[j]) upd(mindiv[j], 1);
    }
    //建树
    for (int i = 2; i <= n; i++) {
        while (top > 1 && dep[st[top - 1]] >= lcadep[i])
            add_edge(st[top - 1], st[top]), top--;
        if (dep[st[top]] != lcadep[i]) 
        {
            dep[++tot] = lcadep[i];
            add_edge(tot, st[top]);
            st[top] = tot;
        }
        st[++top] = i;
    }
    while (top > 1)
    {
        add_edge(st[top - 1], st[top]);
        top--;
    }
}

void dfs(int u, int fa) {
    ans += 1ll * w[u] * dep[u];//ans最开始是rt = 1时的答案
    for (auto &v: g[u])
        if (v != fa) {
            dfs(v, u);
            w[u] += w[v];
        }
}

void dfs2(int u, int fa) {//如果rt移动之后答案变小就一直移动下去，直到答案不在变小
    for (auto &v: g[u])
        if (v != fa) {
            //rt从u转移到v的代价
            //+(w[1] - w[v]) - w[v]
            if (w[1] - 2 * w[v] < 0) {
                ans += 1ll * (w[1] - 2 * w[v]) * (dep[v] - dep[u]);//一步的代价*距离
                dfs2(v, u);
            }
        }
}

void init() {
    ans = top = 0;
    for (int i = 1; i <= tot; i++) 
    {
        g[i].clear();
        c[i] = w[i] = lcadep[i] = dep[i] = 0;
    }
}

int main() {

    sieve(1e5);
    while (~scanf("%d", &n)) {
        init();
        for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
        buildVirtualTree();
        int rt = 1;
        dfs(rt, 0);
        dfs2(rt, 0);
        printf("%lld\n", ans);
    }

    return 0;
}

XCPC 文章被收录于专栏

主要记录ICPC的真题