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↵
↵
<spoiler summary="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"; ↵
}↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
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↵
↵
<spoiler summary="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"; ↵
}↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
