/**
 * @file closing.cpp
 * @author n685
 * @brief
 * @date 2023-12-26
 *
 *
 */
#include "closing.h"
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

using LL = long long;

template <class T> struct CC {
  std::vector<T> val;
  void insert(T a) { val.push_back(a); }
  void init() {
    std::sort(val.begin(), val.end());
    val.erase(std::unique(val.begin(), val.end()), val.end());
  }
  int operator[](T a) const {
    return static_cast<int>(std::distance(
        val.begin(), std::lower_bound(val.begin(), val.end(), a)));
  }
  int size() const { return static_cast<int>(val.size()); }
};

CC<int64_t> cc;
template <class T> struct Seg {
  struct Node {
    using RT = T;
    static constexpr RT ID = 0;
    T val = 0;
    int cnt = 0;

    Node() {}
    Node(T v) : val(v) {}

    operator RT() { return val; }
    static RT comb(RT a, RT b) { return a + b; }
    void add(T v) {
      val += v;
      cnt++;
    }
    void rem(T v) {
      val += v;
      cnt--;
    }
    void pull(Node &ll, Node &rr) {
      val = ll.val + rr.val;
      cnt = ll.cnt + rr.cnt;
    }
  };
  using RT = typename Node::RT;
  int sz = 0;
  std::vector<Node> val;

  Seg() {}
  Seg(int _sz) {
    // sz = _sz;
    if (_sz == 1) {
      sz = 1;
    } else {
      sz = (1 << (std::__lg(_sz - 1) + 1));
    }
    val.resize(2 * sz);
  }
  Seg(const std::vector<T> &v) : Seg(static_cast<int>(v.size())) {
    for (int i = 0; i < static_cast<int>(v.size()); ++i) {
      val[i + sz] = v[i];
    }
    build(0, sz - 1);
  }
  void build(int l, int r) {
    l += sz, r += sz;
    l /= 2, r /= 2;
    for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2) {
      for (int i = l; i <= r; ++i) {
        val[i].pull(val[2 * i], val[2 * i + 1]);
      }
    }
  }
  void upd(int ind, const std::function<void(Node &)> &f) {
    f(val[ind += sz]);
    for (ind /= 2; ind >= 1; ind /= 2) {
      val[ind].pull(val[2 * ind], val[2 * ind + 1]);
    }
  }
  void add(int ind, const T &v) {
    upd(ind, [&v](Node &n) { n.add(v); });
  }
  void rem(int ind, const T &v) {
    upd(ind, [&v](Node &n) { n.rem(v); });
  }
  RT query(int l, int r) {
    RT ll = Node::ID, rr = Node::ID;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1) {
        ll = Node::comb(val[l++], ll);
      }
      if (r % 2 == 0) {
        rr = Node::comb(rr, val[r--]);
      }
    }
    return Node::comb(ll, rr);
  }
  int walk(LL lim, int ind, int l, int r) {
    if (lim < 0) {
      return 0;
    }
    if (l >= cc.size()) {
      return 0;
    }
    if (l == r) {
      if (cc.val[l] == 0) {
        return val[ind].cnt;
      } else {
        return (int)std::min<LL>(val[ind].cnt, lim / cc.val[l]);
      }
    }
    int ll = 0;
    int mid = (l + r) / 2;
    if (val[2 * ind].val <= lim) {
      ll = val[2 * ind].cnt;
      lim -= val[2 * ind].val;
    } else {
      return walk(lim, 2 * ind, l, mid);
    }
    return ll + walk(lim, 2 * ind + 1, mid + 1, r);
  }
  int walk(LL lim) { return walk(lim, 1, 0, sz - 1); }
};

struct Node {
  LL a, b;
};

int max_score(int N, int X, int Y, long long K, std::vector<int> U,
              std::vector<int> V, std::vector<int> W) {
  using ll = long long;
  int n = N, x = X, y = Y; // lowercase better
  ll k = K;
  std::vector<std::vector<std::pair<ll, int>>> adj(N);
  for (int i = 0; i < n - 1; ++i) {
    adj[U[i]].emplace_back(W[i], V[i]);
    adj[V[i]].emplace_back(W[i], U[i]);
  }

  std::vector<ll> dx(n, (ll)4e18), dy(n, (ll)4e18);
  std::vector<bool> cx(n, (ll)4e18), cy(n, (ll)4e18);
  cx[x] = 0;
  cy[y] = 0;
  dx[x] = 0;
  dy[y] = 0;
  auto dfs = [&](auto &self, int node, int par, std::vector<ll> &dist) -> void {
    for (auto [w, i] : adj[node]) {
      if (i == par) {
        continue;
      }
      dist[i] = dist[node] + w;
      cy[i] = cy[node] + dist[node] + w;
      self(self, i, node, dist);
    }
  };
  dfs(dfs, x, -1, dx);
  dfs(dfs, y, -1, dy);

  int ans1 = 0;
  {
    ll kk = k;
    std::vector<int> ind(n);
    std::iota(ind.begin(), ind.end(), 0);
    std::sort(ind.begin(), ind.end(), [&](int a, int b) {
      return std::min(dx[a], dy[a]) < std::min(dx[b], dy[b]);
    });
    for (int i = 0; i < n; ++i) {
      kk -= std::min(dx[ind[i]], dy[ind[i]]);
      if (kk < 0) {
        break;
      }
      ans1++;
    }
  }

  std::vector<int> s;
  int st = 0;
  std::vector<Node> v(n);
  for (int i = 0; i < n; ++i) {
    if (dx[i] + dy[i] != dx[y]) {
      v[i].a = std::min(dx[i], dy[i]);
      v[i].b = std::max(dx[i], dy[i]);
    } else {
      st++;
      k -= std::min(dx[i], dy[i]);
      v[i].a = std::max(dx[i], dy[i]) - std::min(dx[i], dy[i]);
      v[i].b = (int64_t)4e18;
    }
    cc.insert(v[i].a);
    cc.insert(v[i].b - v[i].a);
  }
  if (k < 0) {
    return ans1;
  }
  cc.init();
  std::sort(v.begin(), v.end(), [](const Node &a, const Node &b) {
    return a.b == b.b ? a.a < b.a : a.b < b.b;
  });

  Seg<int64_t> seg(cc.size());
  for (int i = 0; i < n; ++i) {
    seg.add(cc[v[i].a], v[i].a);
  }
  int ans = seg.walk(k);
  for (int i = 0; i < n; ++i) {
    k -= v[i].a;
    seg.rem(cc[v[i].a], v[i].a);
    seg.add(cc[v[i].b - v[i].a], v[i].b - v[i].a);
    if (k < 0) {
      break;
    }
    ans = std::max(ans, i + 1 + seg.walk(k));
  }
  return std::max(ans1, st + ans);
}