#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

//#define int long long
typedef long long ll;
#define pii pair<ll, ll>
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
const int MAXN = 2e5 + 5;
const int MAXM = 4e6 + 5;   // implicit segtree
const int MAX = 1e12 + 5;

ll dist[MAXN][2];
ll a[MAXN], b[MAXN];   // 2 costs
int ans, ans2;  // no overlap, overlap
vector<pii> adj[MAXN];
vector<int> vals;

ll have;

ll tot = 1;
ll val[MAXM], cnt[MAXM];
ll lc[MAXM], rc[MAXM];

void check() {
    if(tot >= MAXM) while(true) cout << "oof";
}

void pull(ll u) {
    val[u] = val[lc[u]] + val[rc[u]];
    cnt[u] = cnt[lc[u]] + cnt[rc[u]];
}

void ins(ll u, ll l, ll r, ll pos, ll freq) {  // segtree indexed by val so pos = val
    check();
    if(l == r) {
//        cout << "updating with " << pos << " " << freq << endl;
        val[u] += pos * freq;
        cnt[u] += freq;
        return;
    }

    ll mid = (l + r) / 2;

    if(pos <= mid) {
        if(lc[u] == 0) lc[u] = ++tot;
        ins(lc[u], l, mid, pos, freq);
    }
    else {
        if(rc[u] == 0) rc[u] = ++tot;
        ins(rc[u], mid + 1, r, pos, freq);
    }
    pull(u);
}

int walk(ll u, ll l, ll r) {
    if(u == 0) return 0;
//    cout << u << " " << l << " " << r << " " << val[u] << " " << cnt[u] << endl;
    if(l == r) {
//        cout << cnt[u] << " " << have << " " << l << endl;
        ll sub = min(cnt[u], have / l);
        have -= l * sub;
//        cout << "returning " << sub << endl;
        return sub;
    }

    ll mid = (l + r) / 2;
    ll ret = 0;
    if(val[lc[u]] > have) return walk(lc[u], l, mid);

//    cout << "left val: " << val[lc[u]] << " node, lc: " << u << " " << lc[u] << endl;
    have -= val[lc[u]];
    if(have) return cnt[lc[u]] + walk(rc[u], mid + 1, r);
    return cnt[lc[u]];
}

void dfs(int u, int p, int type) {
    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        dist[v][type] = dist[u][type] + w;

        dfs(v, u, type);
    }
}

int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
    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]});
    }


    dfs(x, -1, 0); dfs(y, -1, 1);

    for(int i = 0; i < n; ++i) {
        a[i] = min(dist[i][0], dist[i][1]);
        b[i] = max(dist[i][0], dist[i][1]);
    }

    // seperate
    vector<ll> sortedDists;
    for(int i = 0; i < n; ++i) {
        sortedDists.push_back(dist[i][0]); sortedDists.push_back(dist[i][1]);
    }

    sort(all(sortedDists));

    ll tot = k;
    for(auto val : sortedDists) {
        if(tot >= val) {
            ++ans; tot -= val;
        }
        else break;
    }

    // overlap
    bool flag = false;
    ll distXY = dist[y][0];    // dist between x,y

//    cout << "dist between x,y: " << distXY << endl;

    for(int i = 0; i < n; ++i) {
        if(dist[i][0] + dist[i][1] == distXY) { // on the path
//            cout << "node " << i << " is on path" << endl;
            k -= a[i]; ++ans2;  // forced

            if(k < 0) flag = true;

            ins(1, 0, MAX, b[i] - a[i], 1);
//            cout << "need " << b[i] - a[i] << " to turn to 2" << endl;
        }
        else {
            ins(1, 0, MAX, a[i], 1);
//            cout << "need " << a[i] << " for extra" << endl;
        }
    }

//    cout << "total val of tree: " << val[1] << endl;
//
//    cout << "forced overlap: " << ans2 << endl;
//    cout << "have " << k << " left " << endl;
    have = k;
//    cout << "have: " << have << endl;
    ans2 += walk(1, 0, MAX);
//    cout << "total overlap ans: " << ans2 << endl;
    if(flag) ans2 = 0;

    return max(ans, ans2);
}

//signed main() {
//    int n, x, y, k; cin >> n >> x >> y >> k;
//
//    vector<int> u(n - 1), v(n - 1), w(n - 1);
//
//    for(int i = 0; i < n - 1; ++i) cin >> u[i];
//    for(int i = 0; i < n - 1; ++i) cin >> v[i];
//    for(int i = 0; i < n - 1; ++i) cin >> w[i];
//
//    cout << max_score(n, x, y, k, u, v, w) << endl;
//}

answer.code:14:22: warning: overflow in conversion from ‘double’ to ‘int’ changes value from ‘1.000000000005e+12’ to ‘2147483647’ [-Woverflow]
   14 | const int MAX = 1e12 + 5;
      |                 ~~~~~^~~
answer.code: In function ‘int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)’:
answer.code:109:5: error: ‘sort’ was not declared in this scope; did you mean ‘short’?
  109 |     sort(all(sortedDists));
      |     ^~~~
      |     short