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

2024-03-28 20:18:52

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

题解参考博客：https://blog.nowcoder.net/n/df889adfaf824d50ad2291f4d2eb04a2?&toCommentId=6480068

题目大意：

定义 $mindiv(n)$ 是 $n$ 最小的大于1的约数，对于每一个 $i$，$1<=i<=m$ 建了一条边 $(i,\frac{i}{mindiv[i]})$ ，给你一个 $m$ ，表示用m个关键点，每一个关键点的值是 $i!$ ，让你用这m个关键点建一颗树，然后给你 m个 $wi$ 让你求 $min_u\sum_{i=1}^{m}wi*c(u,i!)$ ，其中 $c(u,i!)$ 表示 $u$ 这个点和 $i$ 这个点之间的边的数量，这个 $u$ 则是这棵树上的任意一个点。

题解：

这个题目前置技能点是虚树，如果不会，先学习虚树。

学习博客：https://www.cnblogs.com/EchoZQN/p/13330893.html

学会虚树了，然后开始分析这个题目。

首先为什么要用虚树，这个是因为这棵树太大了，无法存下来。
怎么建虚树？
- 建一棵虚树需要什么：原树关键点的 $dfs$ 序，原数关键点的 $LCA$
- 这两个知道之后，就可以直接套模板了
怎么求原树关键点的 $dfs$ 序？
- 首先我们比较 $i!$ 、$(i+1)!$
- 我们定义 $dfs$ 序：
- $(i+1)!$ 相对于 $i!$ ，多了一个约数 $(i+1)$ ，如果这个 $(i+1)$ 是一个质数，是不是 $(i+1)!$ 的 $dfs$ 序一定在 $i!$ 后面，如果这个不是一个质数，那么如果 $i+1$ 存在约数大于 $i!$ 的最小素因子，那么是不是 $(i+1)!$ 会分向右分叉，如果没有，那就是都等于最小素因子，那么是不是会延长，所以 $(i+1)!$ 的 $dfs$ 序一定大于 $i!$ 。
- 所以最终结果就是对于这 $m$ 个关键点，他们的 $dfs$ 序和本身大小成正比。
接下来说说怎么求 $LCA$
- 假设 $u=p_{1}^{a1}p_{2}^{a1}...p_{x}^{ax}$ $v=p_{1}^{a1}p_{2}^{a2}...p_{y}^{ay}$ （p按照顺序排序）
- 那么，他们相同的节点就是从后往前比较第一个不同的位置，也就是第一个 $(p_i!=p_j||ai!=aj)$ 这个位置就是他们的 $LCA$
- 因为 $dfs$ 序是和本身大小成正比的，所以对于数 $i!$ 和 $(i+1)! $ ，假设 $lca1=LCA((i-1)!,i!)$ ， $lca2=LCA(i!,(i+1)!)$ 只有三种关系：
  - $lca1==lca2$ 直接建边
  - $lca2<lca1$ 重新给这个 $lca$ 一个编号，然后建边
  - $lca2=1$ 直接建边
最后总结一下怎么求 $LCA$
- 首先用线段树维护一下这个位置和栈顶元素的 $LCA$ 的深度
- 这个维护参考上面。
- 假设当前位置是 $p$ ，栈顶元素是 $x$ ，栈第二个元素是 $y$
- 先求 $lca=LCA(p,x)$
  - $dep[lca]==dep[y]$ 说明 $lca=y$
  - $dep[lca]>dep[y]$ 则说明 $lca$ 还在 $y$ 这个节点之上，丢掉栈顶元素，继续判断
  - $dep[lca]<dep[y]$ 说明 $lca$ 还没有入栈，那就给这个 $lca$ 一个编号，然后让他入栈，建边

#include <bits/stdc++.h>
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define debug(x) printf("debug:%s=%d\n",#x,x);
//#define debug(x) cout << #x << ": " << x << endl
using namespace std;
const int maxn = 2e5+10;
typedef long long ll;
int head[maxn<<1],nxt[maxn<<1],to[maxn<<1],cnt;
void ADD(int u,int v){
//    printf("u=%d v=%d\n",u,v);
    ++cnt,to[cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
    ++cnt,to[cnt]=u,nxt[cnt]=head[v],head[v]=cnt;
}

int sum[maxn*4];//Ïß¶ÎÊ÷Î¬»¤lca
void build(int id,int l,int r){
    sum[id]=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
void update(int id,int l,int r,int pos,int val){
    if(l==r){
        sum[id]+=val;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(id<<1,l,mid,pos,val);
    else update(id<<1|1,mid+1,r,pos,val);
    sum[id]=sum[id<<1]+sum[id<<1|1];
}

int query(int id,int l,int r,int x,int y){
    if(x<=l&&y>=r) return sum[id];
    int mid=(l+r)>>1,ans=0;
    if(x<=mid) ans+=query(id<<1,l,mid,x,y);
    if(y>mid) ans+=query(id<<1|1,mid+1,r,x,y);
    return ans;
}

int dep[maxn],w[maxn],stk[maxn],cur,now,n;
int isp[maxn],tot,v[maxn];
void init() {
    tot = 0;
    memset(v,0,sizeof(v));
    for (int i = 2; i < maxn; ++i) {
        if (!v[i]) {
            v[i] = i;
            isp[++tot] = i;
        }
        for (int j = 0; j < tot; ++j) {
            if (1ll * i * isp[j] >= maxn) break;
            v[i * isp[j]] = isp[j];
        }
    }
}
int num;
pair<int,int>prime[maxn];
void judge(int x) {
    int y = x;
    num = 0, dep[y] = 0;
    int f = lower_bound(isp + 1, isp + 1 + tot, 500) - isp;
    for (int i = 1; i <= f; i++) {
        int cur = 0;
        while (x % isp[i] == 0) x /= isp[i], cur++;
        if (cur) prime[++num] = make_pair(i, cur);
        dep[y] += cur;
        if (x == 1) break;
    }
    if (x != 1) {
        dep[y]++;
        int pos = lower_bound(isp + 1, isp + 1 + tot, x) - isp;
        prime[++num] = make_pair(pos, 1);
    }
//    debug(y)
//    debug(dep[y])
}

void modify(){
	for(int i=1;i<=num;i++) update(1,1,n,prime[i].fir,prime[i].sec);
}

void insert(int p) {
//	printf("p=%d\n",p);
    judge(p);
    dep[p]+=dep[p-1];
//    printf("dep[%d]=%d\n",p,dep[p]);
    int x = stk[cur];
    if (x == 1) {
    	modify();
        stk[++cur] = p;
        return;
    }
    int pos = prime[num].fir;
    int d = query(1, 1, n, pos, n);
//    debug(d)
//    debug(dep[stk[cur]])
    while (d != dep[stk[cur]]) {
        int y = stk[--cur];
//        debug(y)
        if(dep[y]<d){
        	++now,dep[now]=d;
			ADD(now,x),stk[++cur]=now;
            break;
        }
        if(dep[y] == d){
        	ADD(y,x);
        	break;
		}
        ADD(x,y),x=stk[cur];
    }
//    debug(cur)
//    debug(stk[cur])
    stk[++cur]=p;
    modify();
}

int m;
ll dp[maxn],have[maxn],ans;

void dfs1(int u,int pre){
//	printf("u=%d\n",u);
    dp[u]=0,have[u]=0;
    if(u<=m&&u>=1) have[u]=w[u];
    for(int i=head[u];i;i=nxt[i]){
        int v = to[i];
        if(v==pre) continue;
        dfs1(v,u);
        have[u]+=have[v];
        ll dis = dep[v]-dep[u];
//        printf("u=%d v=%d dis=%lld\n",u,v,dis);
        dp[u]+=dp[v]+have[v]*dis;
    }
//    printf("dp[%d]=%lld\n",u,dp[u]);
}

void dfs2(int u,int pre){
//	debug(u);
	ans=min(ans,dp[u]);
    for(int i=head[u];i;i=nxt[i]){
        int v = to[i];
        if(v==pre) continue;
        ll dis = dep[v]-dep[u];
//        printf("dp[%d]=%lld dp[%d]=%lld have[%d]=%d have[%d]=%d dis=%lld\n",u,dp[u],v,dp[v],u,have[u],v,have[v],dis);
        dp[v]=dp[u]-have[v]*dis+(have[u]-have[v])*dis;
//        printf("dp[%d]=%lld\n",v,dp[v]);
        have[v]=have[u];
        dfs2(v,u);
    }
	have[u]=0,head[u]=0;
}

void solve(){
    now=m,cnt=0,stk[cur=1]=1;
    for(int i=2;i<=m;i++) insert(i);
    while(--cur) ADD(stk[cur],stk[cur+1]);
	ans = inf64;
    dfs1(1,0),dfs2(1,0);
    printf("%lld\n",ans);
    return ;
}

int main(){
    init();
    while(scanf("%d",&m)!=EOF){
        n = lower_bound(isp+1,isp+1+tot,m)-isp;
        for(int i=1;i<=m;i++) scanf("%d",&w[i]);
        build(1,1,n);solve();
    }
}

码农公寓

相关文章