数据结构算法（Codeforces - Weights Division）

题目链接：Codeforces - Weights Division

---

其实这道题是没啥思维难度的。

我们考虑每条边的贡献，也就是下面的叶子数和当前边的权值。

因为减少的权值只有两种，我们可以用堆来维护每次能减去的最多价值，然后判断两个费用1的和费用2的大小，然后选择最优的即可。不过细节较多。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; int n,s,sz[N],dep[N],u[N],v[N],w[N],c[N],sum; vector<int> g[N]; struct node{int val,sz,w;}; bool operator < (node a,node b){return a.val<b.val;} void dfs(int x,int fa){ sz[x]=(fa&&g[x].size()==1); dep[x]=dep[fa]+1; for(int to:g[x]) if(to!=fa) dfs(to,x),sz[x]+=sz[to]; } void solve(){ cin>>n>>s; sum=0; for(int i=1;i<=n;i++) g[i].clear(); for(int i=1;i<n;i++) cin>>u[i]>>v[i]>>w[i]>>c[i],g[u[i]].push_back(v[i]),g[v[i]].push_back(u[i]); dfs(1,0); for(int i=1;i<n;i++) sum+=(dep[u[i]]>dep[v[i]]?sz[u[i]]:sz[v[i]])*w[i]; priority_queue<node> q1,q2; for(int i=1;i<n;i++){ int szv=(dep[u[i]]>dep[v[i]]?sz[u[i]]:sz[v[i]]); if(c[i]==1) q1.push({(w[i]+1)/2*szv,szv,w[i]}); else q2.push({(w[i]+1)/2*szv,szv,w[i]}); } int nd=sum-s,res=0; if(!q2.size()){ while(nd>0){ node u=q1.top(); q1.pop(); nd-=u.val; res++; u.w/=2; q1.push({(u.w+1)/2*u.sz,u.sz,u.w}); } return cout<<res<<'\n',void(); } if(!q1.size()){ while(nd>0){ node u=q2.top(); q2.pop(); nd-=u.val; res+=2; u.w/=2; q2.push({(u.w+1)/2*u.sz,u.sz,u.w}); } return cout<<res<<'\n',void(); } while(nd>0){ node u=q1.top(); q1.pop(); if(u.val>=nd){res++; break;} if(q2.top().val>=nd){res+=2; break;} int mx=((u.w/2)+1)/2*u.sz; if(q1.size()) mx=max(mx,q1.top().val); if(u.val+mx>q2.top().val){ nd-=u.val; res++; u.w/=2; q1.push({(u.w+1)/2*u.sz,u.sz,u.w}); }else{ q1.push(u); res+=2; nd-=q2.top().val; u=q2.top(); q2.pop(); u.w/=2; q2.push({(u.w+1)/2*u.sz,u.sz,u.w}); } } cout<<res<<'\n'; } signed main(){ ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr); int T; cin>>T; while(T--) solve(); return 0; } 

本文地址：https://blog.csdn.net/weixin_43826249/article/details/107860596