#include "closing.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <tuple>
#include <queue>
#define ff first
#define ss second
using namespace std;
struct Tree {
int n;
vector<vector<pair<int, long long>>> adj;
Tree(int _n) : n(_n), adj(n) {}
void add_edge(int u, int v, long long w) {
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<long long> distance(int root) {
vector<long long> dis(n);
auto dfs = [&] (auto dfs, int u, int p) -> void {
for (auto [v, w]: adj[u]) {
if (v == p) continue;
dis[v] = dis[u] + w;
dfs(dfs, v, u);
}
};
dfs(dfs, root, -1);
return dis;
}
int solve(int x, int y, long long k) {
int ans = 0;
vector<vector<long long>> dis(2);
dis[0] = distance(x);
dis[1] = distance(y);
vector<long long> c(n);
long long cost = 0;
using pqe = tuple<long long, long long, int, int>;
priority_queue<pqe, vector<pqe>, greater<pqe>> pq;
pq.push({0, dis[1][x], x, 0});
pq.push({0, dis[0][y], y, 1});
vector<vector<bool>> vis(2, vector<bool>(n));
while (pq.size()) {
auto [s, nex, u, f] = pq.top(); pq.pop();
if (vis[f][u]) continue;
if (cost + s > k) break;
cost += s;
c[u] += s;
vis[f][u] = true;
ans++;
bool ok = false;
for (auto [v, w]: adj[u]) {
if (vis[f^1][v]) ok = true;
if (vis[f][v]) continue;
pq.push({max(0ll, dis[f][v] - c[v]), dis[f][v] <= dis[f^1][v] ? dis[f^1][v] - dis[f][v] : (long long)1e18, v, f});
}
if (ok) {
pq.push({max(0ll, dis[f^1][u] - c[u]), (long long)1e18, u, f^1});
}
}
return ans;
}
};
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
Tree t(N);
for (int i=0; i<N-1; i++) t.add_edge(U[i], V[i], W[i]);
return t.solve(X, Y, K);
}
