关于虚树上 dp
查看原帖
关于虚树上 dp
483966
一粒夸克楼主2021/9/11 19:05

计算虚树上任意两点的距离和时,为什么不能直接用边长乘以跨过这条边的点对

0分代码:

for(auto it : vec){
    if(it<=n)stk[++top]=it;
    else {
        int u=stk[top--];
        if(top){
            int x=stk[top],dis=dep[u]-dep[x];
            ans1+=1ll*dis*(k-siz[u]);siz[x]+=siz[u];
            mn[u]+=dis;ans2=min(ans2,mn[u]+mn[x]);mn[x]=min(mn[x],mn[u]);
            mx[u]+=dis;ans3=max(ans3,mx[u]+mx[x]);mx[x]=max(mx[x],mx[u]);
        }siz[u]=0;mn[u]=1e9;mx[u]=0;vis[u]=0;
    }
}

满分代码:

for(auto it : vec){
    if(it<=n)stk[++top]=it;
    else {
        int u=stk[top--];
        if(top){
        int x=stk[top],dis=dep[u]-dep[x];
            sum[u]+=siz[u]*dis;
            ans1+=siz[u]*sum[x]+siz[x]*sum[u];
            siz[x]+=siz[u];sum[x]+=sum[u];
            mn[u]+=dis;ans2=min(ans2,mn[u]+mn[x]);mn[x]=min(mn[x],mn[u]);
            mx[u]+=dis;ans3=max(ans3,mx[u]+mx[x]);mx[x]=max(mx[x],mx[u]);
        }siz[u]=0;mn[u]=1e9;mx[u]=0;vis[u]=0;sum[u]=0;
    }
}
2021/9/11 19:05
加载中...