func_code_string: #include <bits/stdc++.h>   using namespace std;   template <class A, class B>   ostream& operator<<(ostream& out, const pair<A, B>& a) {     return out <<  (  << a.first <<  ,   << a.second <<  ) ;   }   template <class A>   ostream& operator<<(ostream& out, const vector<A>& v) {     out <<  [ ;     for (int i = 0; i < v.size(); i++) {       if (i) out <<  ,  ;       out << v[i];     }     return out <<  ] ;   }   bool Check(int n, int pos) { return (bool)(n & (1 << pos)); }   struct edg {     long long to, w, c;   };   vector<edg> g[100005];   vector<long long> v1, v2;   int vis[100005];   long long sum, s;   void calc(long long ws, long long lf, long long c) {     while (ws) {       long long wy = ws;       ws /= 2LL;       wy = wy - ws;       if (c == 1)         v1.emplace_back(wy * lf);       else         v2.emplace_back(wy * lf);     }   }   long long dfs(long long i, long long ws) {     vis[i] = 1;     long long ret = 0;     bool is_leaf = true;     for (auto j : g[i]) {       if (vis[j.to] == -1) {         is_leaf = false;         int r = dfs(j.to, ws + j.w);         ret += r;         calc(j.w, r, j.c);       }     }     if (is_leaf) {       sum += ws;       return 1LL;     }     return ret;   }   void solve() {     int n;     cin >> n >> s;     for (int i = 1; i < n; i++) {       int u, v, w, c;       cin >> u >> v >> w >> c;       u--, v--;       g[u].push_back({v, w, c});       g[v].push_back({u, w, c});     }     memset(vis, -1, sizeof(vis));     dfs(0, 0);     sort(v1.begin(), v1.end(), greater<long long>());     sort(v2.begin(), v2.end(), greater<long long>());     int len1 = v1.size();     int len2 = v2.size();     long long res = 0;     int i = -1, j = 0;     while (sum > s && i + 1 < len1) {       res++;       i++;       sum -= v1[i];     }     while (sum > s && j < len2) {       res += 2;       sum -= v2[j];       j++;     }     long long cur = res;     while (i >= 0) {       sum += v1[i];       cur--;       i--;       while (sum > s && j < len2) {         sum -= v2[j];         cur += 2;         j++;       }       if (sum <= s) {         res = min(res, cur);       }     }     cout << res <<   n ;     for (int i = 0; i <= n; i++) g[i].clear();     v1.clear();     v2.clear();     sum = 0;   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL);     cout.tie(NULL);     int q = 1;     cin >> q;     for (int kase = 1; kase <= q; kase++) {       solve();     }     return 0;   }   