题目链接
思路：
先计算每条边被计算的次数，然后贪心地每次减半能减少最多花费的边，直到小于等于S为止。
代码：
#include<bits/stdc++.h>
#define ll long long
#define LL long long
#define PB push_back
#define MP make_pair
using namespace std;
const int maxn=2e5+100;
const ll inf=1e18+10;
ll n,s,val[maxn],len[maxn];
struct node{ll u,to,v,id;
};
struct node2{ll ti,val,id;
};
bool operator<(node2 a, node2 b){return a.ti*(a.val-a.val/2)<b.ti*(b.val-b.val/2);
}
vector<node>g[maxn];
ll dfs(int pre,int u){int sz=g[u].size();ll sum=0;if(sz==1&&u!=1)return 1;for(int i=0;i<sz;i++){ll to=g[u][i].to,v=g[u][i].v,id=g[u][i].id;if(to==pre)continue;val[id]=dfs(u,to);sum+=val[id];}return sum;
}
void slove(){scanf("%lld%lld",&n,&s);for(int i=1;i<=n;i++)g[i].clear(),val[i]=len[i]=0;for(int i=1;i<n;i++){val[i]=0;ll x,y,v;scanf("%lld%lld%lld",&x,&y,&v);g[x].PB(node{x,y,v,i});g[y].PB(node{y,x,v,i});len[i]=v;}dfs(0,1);ll sum=0;priority_queue<node2>q;for(int i=1;i<n;i++){sum+=val[i]*len[i];q.push(node2{val[i],len[i],i});}ll ans=0;while(sum>s){ans++;node2 x=q.top();q.pop();sum-=x.ti*(x.val-x.val/2);q.push(node2{x.ti,x.val/2,x.id});}printf("%lld\n",ans);
}
int main(){int t;scanf("%d",&t);while(t--){slove();}return 0;
}