#include "closing.h"
#include <iostream>
#include <algorithm>
#include <cassert>
#include <vector>
using ll = long long;
const int NMAX = 2e5;
const ll INF = 1e18;
std::vector<std::vector<std::pair<int, int>>> g;
void dfs(int u, int p, std::vector<ll> &d) {
for (const auto &[v, c] : g[u]) {
if (v != p) {
d[v] = d[u] + c;
dfs(v, u, d);
}
}
}
int max_score(int n, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
g.clear();
g.resize(n);
for (int i = 0; i < n - 1; i++) {
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
std::vector<ll> dx(n, 0), dy(n, 0);
dfs(X, -1, dx);
dfs(Y, -1, dy);
std::vector<ll> a(n), b(n);
for (int i = 0; i < n; i++) {
a[i] = std::min(dx[i], dy[i]);
b[i] = std::max(dx[i], dy[i]);
}
// for (int i = 0; i < n; i++) {
// std::cout << a[i] << ' ' << b[i] << '\n';
// }
// std::cout << "\n\n";
// sunt linie si am cel putin unu care apare de doua ori
ll aux = K;
for (int i = X + 1; i < Y; i++) {
K -= a[i];
}
std::vector<int> upgrades;
for (int i = 0; i < n; i++) {
if (X < i && i < Y) {
upgrades.push_back(b[i] - a[i]);
} else {
upgrades.push_back(a[i]);
}
}
std::sort(upgrades.begin(), upgrades.end());
int caz1 = Y - X - 1;
if (K < 0) {
caz1 = -1e9;
}
for (const auto &x : upgrades) {
if (K >= x) {
caz1++;
K -= x;
} else {
break;
}
}
upgrades.clear();
for (int i = 0; i < n; i++) {
upgrades.push_back(a[i]);
}
std::sort(upgrades.begin(), upgrades.end());
int caz2 = 0;
K = aux;
for (const auto &x : upgrades) {
if (K >= x) {
caz2++;
K -= x;
}
}
return std::max(caz1, caz2);
}
