This code is failing for test case
5 50
1 3 100
1 5 10
2 3 123
5 4 55
Ans — 8,
Output — 9
anyone, please help me with this problem. ThankYou
Code
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define LL long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define FOR(i, j, k) for (auto i=j ; i<k ; i++)
const long long INF = 1e18;
const long long MAX = 2e5+10;
LL sum=0;
int dfs(int u, int p,vector<pair<LL,LL>>adj[],vector<int>&vis,priority_queue<pair<LL,LL>>&w,LL l){
vis[u]=1; int cnt=0,le=0,tt;
for(auto v : adj[u])
if(!vis[v.first]){
tt=dfs(v.first,u,adj,vis,w,l+v.second);
le+=tt; cnt++;
w.push({v.second*tt,v.second});
}
if(cnt==0) {sum+=l; return 1; }
return le;
}
int main(){
fastio;
int t=1; cin>>t;
while(t--){
LL n,s; cin>>n>>s;sum=0;
vector<pair<LL,LL>>adj[n+1]; priority_queue<pair<LL,LL>>w; vector<int>vis(n+1,0);
FOR(i,0,n-1){
LL u,v,w; cin>>u>>v>>w;
adj[u].push_back({v,w}); adj[v].push_back({u,w});
}
dfs(1,-1,adj,vis,w,0);
int ans = 0;
while(sum>s && !w.empty()) {
auto q = w.top(); w.pop();
if(q.second)
sum-=q.first/2,w.push({q.first/2,q.second/2}),ans++;
}
cout<<ans<<"\n";
}
}