#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// cope counter = 2254

vector<pair<ll, ll>> adj[200001];
ll dis[2][200001], cnt[200001];

void dfs(ll i, ll p, ll idk) {
    for(auto j : adj[i]) {
        if(j.f == p) continue;
        dis[idk][j.f] = dis[idk][i] + j.s;
        dfs(j.f, i, idk);
    }
}

struct kms {
    ll cost;
    ll idx, type;
    kms() {
        cost = 1e18, idx = 0, type = 0;
    }
    kms(ll a, ll b, ll c) {
        cost = a, idx = b, type = c;
    }
};
struct comp {
    bool operator()(kms &a, kms &b) {
        return a.cost > b.cost;
    }
};

ll max_score(ll n, ll x, ll y, ll k, vector<ll> u, vector<ll> v, vector<ll> w) {
	ll kk = k;
	for(ll i = 0; i < n; i++) adj[i].clear(), cnt[i] = 0;
    for(ll i = 0; i < n - 1; i++) {
        adj[u[i]].push_back(mp(v[i], w[i]));
        adj[v[i]].push_back(mp(u[i], w[i]));
    }
    dis[0][x] = dis[1][y] = 0;
    dfs(x, x, 0), dfs(y, y, 1);
    ll ans = 0;
    priority_queue<kms, vector<kms>, comp> bk1, bk2;
    ll idfk = dis[0][y];
    for(ll i = 0; i < n; i++) {
        if(dis[0][i] + dis[1][i] == idfk) {
            ans++, cnt[i]++;
            k -= min(dis[0][i], dis[1][i]);
            bk1.push(kms(abs(dis[0][i] - dis[1][i]), i, 1));
        } else {
            bk1.push(kms(min(dis[0][i], dis[1][i]), i, 0));
            bk2.push(kms(max(dis[0][i], dis[1][i]), i, 0));
        }
    }
    while(1) {
        while(!bk1.empty() && (k < bk1.top().cost || cnt[bk1.top().idx] != bk1.top().type)) bk1.pop();
        while(!bk2.empty() && (k < bk2.top().cost || cnt[bk2.top().idx] != bk2.top().type)) bk2.pop();
        if(bk1.empty() && bk2.empty()) break;
        kms idk1, idk2, idk3;
        if(!bk1.empty()) {
            idk1 = bk1.top();
            bk1.pop();
            cnt[idk1.idx]++;
            while(!bk1.empty() && (k < bk1.top().cost || cnt[bk1.top().idx] != bk1.top().type)) bk1.pop();
            cnt[idk1.idx]--;
            if(!bk1.empty()) idk2 = bk1.top();
        }
        if(!bk2.empty()) idk3 = bk2.top();
        if(bk2.empty() || idk1.cost + idk2.cost < idk3.cost)
        {
            k -= idk1.cost;
            ans++, cnt[idk1.idx]++;
            if(cnt[idk1.idx] == 1) bk1.push(kms(abs(dis[0][idk1.idx] - dis[1][idk1.idx]), idk1.idx, 1));
        } else {
            bk1.push(idk1);
            k -= min(dis[0][idk3.idx], dis[1][idk3.idx]);
            ans++;
            cnt[idk3.idx]++;
            bk1.push(kms(abs(dis[0][idk3.idx] - dis[1][idk3.idx]), idk3.idx, 1));
            bk2.pop();
        }
    }
    if(k < 0) ans = 0;
    ll ans2 = 0;
    ll dist[2 * n];
    for(ll i = 0; i < n; i++) dist[i] = dis[0][i], dist[i + n] = dis[1][i];
    sort(dist, dist + 2 * n);
    for(ll i = 0; i < 2 * n; i++) {
        if(kk - dist[i] < 0) break;
        ans2++;
        kk -= dist[i];
    }
    return max(ans, ans2);
}

/usr/bin/ld: /tmp/cc6kKdbC.o: in function `main':
implementer.cpp:(.text.startup+0x775): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status