#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
template <class T>
class pointsegtree {
public:
    int n;
    T inf = 2e18;
    vector<T> t;
    vector<int> cnt;
    pointsegtree(int n) {
        this->n = n;
        t.resize(n * 4);
        cnt.resize(n * 4);
    }
    
    void update(int p, T x, int c, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = x, cnt[v] = c;
            return;
        }
        
        int mid = (tl + tr) / 2;
        if (p <= mid) update(p, x, c, v * 2, tl, mid);
        else update(p, x, c, v * 2 + 1, mid + 1, tr);
        t[v] = t[v * 2] + t[v * 2 + 1];
        t[v] = min(t[v], inf);
        cnt[v] = cnt[v * 2] + cnt[v * 2 + 1];
    }
    
    void update(int p, T x, int c) {
        update(p, x, c, 1, 0, n - 1);
    }
    
    int query(T c, int v, int tl, int tr) {
        if (tl == tr) return t[v] > c ? 0 : cnt[v];
        int mid = (tl + tr) / 2;
        if (t[v * 2] >= c) return query(c, v * 2, tl, mid);
        else return cnt[v * 2] + query(c - t[v * 2], v * 2 + 1, mid + 1, tr);
    }
    
    int query(T c) {
        return query(c, 1, 0, n - 1);
    }
};

const ll inf = 2e18;
void dfs(int u, vector<vector<pi>> &adj, vector<ll> &d, vector<int> &p) {
    for (auto [v, w] : adj[u]) {
        if (v != p[u]) {
            d[v] = d[u] + w, p[v] = u;
            dfs(v, adj, d, p);
        }
    }
}

int slv(int n, vector<ll> &aa, vector<ll> &bb, ll k) {
    vector<pll> a(n);
    vector<vector<int>> b(n, vector<int>(2));
    dbg(aa);
    dbg(bb);
    for (int i = 0; i < n; i++) {
        a[i] = {bb[i], aa[i]};
    }
    
    sort(a.begin(), a.end());
    dbg(a);
    vector<pair<ll, pi>> vals(2 * n);
    for (int i = 0; i < n; i++) {
        auto [y, x] = a[i];
        vals[i * 2] = {x, {i, 0}};
        vals[i * 2 + 1] = {y - x, {i, 1}};
    }
    
    sort(vals.begin(), vals.end());
    pointsegtree<ll> st(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        auto [v, pa] = vals[i];
        auto [p, t] = pa;
        if (!t) {
            dbgm(v, p, t);
            st.update(i, v, 1);
        }
         
        b[p][t] = i;
    }
    
    dbg(b);
    int out = 0;
    for (int i = 0; i <= n; i++) {
        if (k < 0) break;
        out = max(out, i + st.query(k));
        auto [y, x] = a[i];
        dbgm(out, k, i, st.query(k));
        k -= x;
        if (i == n) break;
        st.update(b[i][0], 0, 0);
        st.update(b[i][1], y - x, 1);
    }
    
    return out;
}

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    vector<vector<pi>> adj(n);
    vector<ll> dx(n, inf), dy(n, inf), a(n), b(n);
    vector<int> px(n), py(n);
    for (int i = 0; i < n - 1; i++) {
        adj[u[i]].push_back({v[i], w[i]});
        adj[v[i]].push_back({u[i], w[i]});
    }
    
    dx[x] = dy[y] = 0, px[x] = py[y] = -1;
    dfs(x, adj, dx, px);
    dfs(y, adj, dy, py);
    int out = 0;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        a[i] = min(dx[i], dy[i]), b[i] = max(dx[i], dy[i]);
        c[i] = a[i];
    }
    
    sort(c.begin(), c.end());
    ll cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur + c[i] > k) break;
        cur += c[i], out++;
    }
    
    // dbg(dx);
    // dbg(dy);
    // dbg(px);
    // dbg(py);
    // dbg(out);
    if (cur > k) return out;
    cur = 0;
    int uu = y, cnt = 0;
    while (true) {
        cur += a[uu], cnt++;
        b[uu] -= a[uu];
        swap(b[uu], a[uu]);
        b[uu] = inf;
        if (uu == x) break;
        uu = px[uu];
    }
    
    k -= cur;
    return max(out, cnt + slv(n, a, b, k));
}

// void solve() {
// // •   DO NOT GET STUCK ON ONE APPROACH!
// // •   Refusing to switch problems is the sign of tunnel vison
// // •   REREAD!
// // •   REMEMBER THAT ALL THAT MATTERS IS THE TOTAL SCORE!
// // •   GET SUBTASKS!
// // •   Plan the rest of the contest out!
// // •   Look at the constraints
// // •   Look for edge cases like n = 1
// // •   Set bounds of stress tests randomly
// // •   Think more, mindlessly debug less
// // •   Graphs can be disconnected
// // •   Integer overflow
// // •   READ the SAMPLES!
// // When stuck on ideas:
// // •   DFS trees
//     // int out = max_score(7, 0, 2, 10, {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3});
//     // int out = max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19});
//     int out = max_score(8, 0, 1, 14, {0, 0, 0, 0, 1, 1, 1}, {1, 2, 3, 4, 5, 6, 7}, {1, 4, 3, 5, 5, 1, 2});
//     cout << out << "\n";
// }

// int32_t main() {
//     std::ios::sync_with_stdio(false);
//     cin.tie(NULL);
//     solve();
// }