How to fix Tl?

Question

C++ / C#

There is a problem: https://codeforces.com/contest/1399/problem/E1
Here is the code:

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
struct cmp {
  bool operator() (const long long& a, const long long& b) const {
    return a > b;
  }
};
set<long long,cmp>se;
set<int>vis;
long long all = 0;
int dfs(int v,vector <vector<pair<int, int>>>& g) {
  if (g[v].size() == 1&&v!=1) {
    return 1;
  }
  int ans = 0;
  for (auto c : g[v]) {
    if (vis.find(c.first)==vis.end()) {
      int cur = 0;
      vis.insert(c.first);
      cur+=dfs(c.first,g);// сколько листьев при переходе
      se.insert(c.second* cur);
      all += c.second * cur;
      ans += cur;
    }
  }
  return ans;// сколько листьев в поддереве с корнем в вершине v
}
int main() {
  IOS;
  int t;
  cin >> t;
  while (t--) {
    all = 0;
    se.clear();
    vis.clear();
    int n, s;
    cin >> n >> s;
    vector <vector<pair<int, int>>>g(n+1);
    for (int i = 0; i < n - 1; i++) {
      int v, u, w;
      cin >> v >> u >> w;
      g[v].push_back({ u,w });
      g[u].push_back({ v,w });
    }
    vis.insert(1);
    dfs(1,g);
    long long ans = 0;
    while (all > s) {
      long long cur = *se.begin();
      se.erase(cur);
      ans++;
      all -= cur;
      all += cur / 2;
      se.insert(cur/2);
    }
    cout << ans << "\n";
  }
}

I get TL on the 2nd test, why I can't understand (maybe the solution freezes). Thanks in advance for your help!
PS The competition is already over

Answer 1

Try to read through scanf.
I see you are doing via sync_with_stdio(0) but I'm not sure if that helps 100%.
Then, instead of set vis, it is enough to pass the previous vertex to dfs and not go to it.
And yet you have an error, when dividing an edge in half, you cannot divide cnt*w in half. If cnt is even and w is odd, you lose rounding. It is necessary to shove a couple of cnt, w into the heap, and take the maximum cnt*ceil(w/2). And yet, you shove into the heap the cost of an edge, multiplied by the number of leaves along this edge and all the previous ones in the current vertex! It is necessary not to take cur there, but the value of dfs.
And yet, it most likely hangs due to overflow. When multiplying cur*c.second, a negative number can turn out, but you multiply ints, and only then cast to long long.

Answer 2

See task breakdown