#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 2e5 + 5;

constexpr long long inf = (long long)(1e18) + 7;

vector<pair<int, int>> g[maxn];

long long dist_x[maxn], dist_y[maxn];

int prv[maxn];

vector<int> path;

void dfs(int v, long long* dist) {
    for (auto [u, c] : g[v]) {
        if (u != prv[v]) {
            prv[u] = v;
            dist[u] = dist[v] + c;
            dfs(u, dist);
        }
    }
}

void calc_dist(int x, int y) {
    prv[x] = x;
    dfs(x, dist_x);
    prv[y] = y;
    dfs(y, dist_y);
    int nw = x;
    while (nw != y) {
        path.push_back(nw);
        nw = prv[nw];
    }
    path.push_back(y);
}

bool used[maxn];

constexpr int maxn2 = 3005;

long long dp[maxn2][maxn2 * 2][4];

long long res[maxn2 * 2], pr_res[maxn2 * 2], suff_res[maxn2][maxn2 * 2];

vector<int> tree[maxn];

int sz[maxn];

void get_tree(int v, int prv, int root) {
    for (auto [u, c] : g[v]) {
        if (!used[u] && u != prv) {
            tree[root].push_back(u);
            get_tree(u, v, root);
        }
    }
}

int max_score(int n, int x, int y, long long k, vector<int> u,
              vector<int> v, vector<int> w) {
    path.clear();
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        dist_x[i] = dist_y[i] = 0;
        used[i] = false;
        tree[i].clear();
    }
    for (int i = 0; i < n - 1; ++i) {
        g[u[i]].emplace_back(v[i], w[i]);
        g[v[i]].emplace_back(u[i], w[i]);
    }
    calc_dist(x, y);
    int ans = 0;
    long long k_old = k;
    multiset<long long> ms;
    for (int i = 0; i < n; ++i) {
        ms.insert(dist_x[i]);
        ms.insert(dist_y[i]);
    }
    while (!ms.empty() && *ms.begin() <= k) {
        k -= *ms.begin();
        ms.erase(ms.begin());
        ans++;
    }
    if (n > maxn2) {
        return ans;
    }
    for (int i = 0; i < n; ++i) {
        for (int cnt = 0; cnt < maxn2 * 2; ++cnt) {
            for (int mask = 0; mask < 4; ++mask) {
                dp[i][cnt][mask] = inf;
            }
        }
        dp[i][0][0] = 0;
        dp[i][1][1] = dist_x[i];
        dp[i][1][2] = dist_y[i];
        dp[i][2][3] = max(dist_x[i], dist_y[i]);
    }
    k = k_old;
    for (auto v : path) {
        used[v] = true;
    }
    for (auto v : path) {
        get_tree(v, v, v);
        for (int cnt = 0; cnt <= tree[v].size() * 2; ++cnt) {
            for (int mask = 0; mask < 4; ++mask) {
                dp[v][cnt][mask] = inf;
            }
        }
        dp[v][0][0] = dp[v][0][1] = dp[v][0][2] = dp[v][0][3] = 0;
        if (dist_x[v] <= dist_y[v]) {
            vector<long long> vals;
            for (auto u : tree[v]) {
                vals.push_back(dist_x[u]);
            }
            sort(vals.begin(), vals.end());
            for (int cnt = 0; cnt < (int)tree[v].size(); ++cnt) {
                dp[v][cnt + 1][1] = min(dp[v][cnt + 1][1], dp[v][cnt][1] + vals[cnt]);
            }
        } else {
            vector<long long> vals;
            for (auto u : tree[v]) {
                vals.push_back(dist_y[u]);
            }
            sort(vals.begin(), vals.end());
            for (int cnt = 0; cnt < (int)tree[v].size(); ++cnt) {
                dp[v][cnt + 1][2] = min(dp[v][cnt + 1][2], dp[v][cnt][2] + vals[cnt]);
            }
        }
        long long dv = abs(dist_x[v] - dist_y[v]);
        for (int cnt = (int)tree[v].size(); cnt >= 0; --cnt) {
            for (int cnt_add = cnt; cnt_add >= 0; --cnt_add) {
                dp[v][cnt + cnt_add][3] = min(dp[v][cnt + cnt_add][3], min(dp[v][cnt][1], dp[v][cnt][2]) + dv * cnt_add);
            }
        }
        sz[v] = tree[v].size();
        // cout << "!" << ' ' << v << ' ' << dp[v][2][0] << ' ' << dp[v][2][1] << ' ' << dp[v][2][2] << ' ' << dp[v][2][3] << endl;
    }
    pr_res[0] = 0;
    for (int i = 1; i <= n * 2; ++i) {
        pr_res[i] = inf;
    }
    suff_res[path.size()][0] = 0;
    for (int i = 1; i <= n * 2; ++i) {
        suff_res[path.size()][i] = inf;
    }
    for (int i = (int)path.size() - 1; i >= 0; --i) {
        for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
            suff_res[i][cnt_nw] = suff_res[i + 1][cnt_nw];
            if (suff_res[i + 1][cnt_nw] == inf) {
                continue;
            }
            for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                suff_res[i][cnt_nw + cnt_add] = min(suff_res[i][cnt_nw + cnt_add], suff_res[i + 1][cnt_nw] + dp[path[i]][cnt_add][2]);
            }
        }
    }
    for (int l = 0; l < (int)path.size(); ++l) {
        for (int i = 0; i <= n * 2; ++i) {
            res[i] = pr_res[i];
        }
        int add_ans = 0;
        long long add_k = 0;
        for (int i = 0; i < l; ++i) {
            add_ans++;
            add_k += dist_x[path[i]];
        }
        for (int i = l; i < (int)path.size(); ++i) {
            add_ans++;
            add_k += dist_y[path[i]];
        }
        for (int r = l + 1; r <= (int)path.size(); ++r) {
            for (int i = r - 1; i < r; ++i) {
                add_ans++;
                add_k -= dist_y[path[i]];
                add_k += max(dist_x[path[i]], dist_y[path[i]]);
                if (i == r - 1) {
                    for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
                        if (res[cnt_nw] == inf) {
                            continue;
                        }
                        for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                            res[cnt_nw + cnt_add] = min(res[cnt_nw + cnt_add], res[cnt_nw] + dp[path[i]][cnt_add][3]);
                            // if (res[cnt_nw + cnt_add] + add_k <= k) {
                            //     int pos = upper_bound(suff_res[r], suff_res[r] + n * 2, k - res[cnt_nw + cnt_add] - add_k) - suff_res[r] - 1;
                            //     ans = max(ans, cnt_nw + cnt_add + add_ans + pos);
                            // }
                        }
                    }
                }
            }
            ans = max(ans, add_ans);
            while (true) {
                bool change = false;
                if (add_k > k) {
                    break;
                }
                if (add_ans > ans) {
                    ans = add_ans;
                }
                for (int cnt = 0; cnt <= n * 2; ++cnt) {
                    while (ans < n * 2) {
                        if (res[cnt] + add_k + suff_res[r][ans + 1 - cnt - add_ans] <= k) {
                            change = true;
                            ans++;
                        } else {
                            break;
                        }
                    }
                }
                if (!change) {
                    break;
                }
            }
        }
        for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
            if (pr_res[cnt_nw] == inf) {
                continue;
            }
            for (int cnt_add = 0; cnt_add <= sz[path[l]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
                pr_res[cnt_nw + cnt_add] = min(pr_res[cnt_nw + cnt_add], pr_res[cnt_nw] + dp[path[l]][cnt_add][1]);
            }
        }
    }
    return ans;
}