计算虚树上任意两点的距离和时,为什么不能直接用边长乘以跨过这条边的点对
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;
}
}