CF1399E2 Weights Division (hard version) 题解
对于两种权值的分别贪心维护，最后枚举一种权值选多少个，另一个二分出来，总复杂度 \(2\log\)。
点击查看代码
#include
#include
#include
typedef long long ll;
inline int min(const int &a,const int &b){return a t1,t2;
inline void add_edge(int u,int v,int w,int c){e[++tot]=(Edge){v,w,c,h[u]};h[u]=tot;}
void dfs(int u,int fa){
bool son=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa) continue;
val[v]=e[i].w,cost[v]=e[i].c;
dfs(v,u);siz[u]+=siz[v],son=1;
}
if(!son) siz[u]=1;
}
int main(){int T;scanf("%d",&T);while(T--){
scanf("%d%lld",&n,&S);
for(int i=1;i<=n;++i) h[i]=siz[i]=0;tot=0;
for(int i=1;i>=1;
if(val[u]) t1.push(Node(u));
}
while(!t2.empty()){
int u=t2.top().x;t2.pop();
a2[++cnt2]=a2[cnt2-1]+((ll)val[u]+1)/2*siz[u];
val[u]>>=1;
if(val[u]) t2.push(Node(u));
}
int ans=INF;
for(int i=0;i<=cnt1;++i){
if(Sum-a1[i]<=S){ans=min(ans,i);break;}
if(Sum-a1[i]-a2[cnt2]>S) continue;
int l=0,r=cnt2;
while(l>1;
if(Sum-a1[i]-a2[mid]<=S) r=mid;
else l=mid+1;
}
ans=min(ans,i+2*l);
}
printf("%d\n",ans);
}
return 0;
}