#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);

    const ll INF = 2e18;
    vector dp(N+1, vector(N*2+1, INF));
    dp[0][0] = 0;

    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]);
            
            // 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]));
        }
    }

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

    return ans;
}