#include "closing.h"

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

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 data = tuple<ll, int, int, int>;
    vector<ll> dx(N, 0LL), dy(N, 0LL);

    vector adj(N, vector<pair<int,int>>());
    for(int i = 0; i < U.size(); ++i) {
        adj[U[i]].emplace_back(V[i], W[i]);
        adj[V[i]].emplace_back(U[i], W[i]);
    }

    const auto dfs = [&](const auto &self, vector<ll> &d, int node, int from) -> void {
        for(auto &[next, c] : adj[node]) {
            if(next == from) continue;
            d[next] = d[node] + c;
            self(self, d, next, node);
        }
    };
    dfs(dfs, dx, X, -1);
    dfs(dfs, dy, Y, -1);
    int ans = 0;

    {
        // no cities are visited by 2 sources
        vector<ll> v;
        for(int i = 0; i < N; ++i) {
            v.emplace_back(min(dx[i], dy[i]));
        }
        sort(v.begin(), v.end());

        ll sum = 0;
        for(auto &i : v) {
            if(sum + i > K) break;
            ans++;
            sum += i;
        }
    }

    vector<int> path;
    for(int i = 0; i < N; ++i) {
        if(dx[i] + dy[i] == dx[Y]) path.emplace_back(i);
    }

    ll sum = 0;
    for(auto &i : path) {
        sum += min(dx[i], dy[i]);
    }

    const ll INF = 2e18;
    vector dp(N+1, vector(N*2+1, INF));
    vector inpath(N, false);
    for(auto &i : path) inpath[i] = true;

    dp[0][(int)path.size()] = sum;

    for(int i = 0; i < N; ++i) {
        for(int j = 0; j <= N * 2; ++j) {
            if(dp[i][j] == INF) continue;

            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);

            if(!inpath[i]) {
                // visit once
                if(j + 1 <= N * 2) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + min(dx[i], dy[i]));

                // visit twice
                if(j + 2 <= N * 2) dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j] + max(dx[i], dy[i]));
            }
            else {
                // visit once more
                if(j + 1 <= N * 2) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + max(dx[i], dy[i]) - min(dx[i], dy[i]));
            }
        }
    }

    for(int i = 0; i <= N * 2; ++i) {
        if(dp[N][i] <= K) ans = max(ans, i);
    }

    return ans;
}