#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 easy_solve(int x, int y, long long k) {
using pii = pair<long long, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, x});
pq.push({0, y});
long long cost = 0;
int ans = 0;
vector<bool> vis(n);
while (pq.size()) {
auto [d, u] = pq.top(); pq.pop();
if ((cost += d) <= k) ans++;
else break;
vis[u] = true;
for (auto [v, w]: adj[u]) {
if (vis[v]) continue;
pq.push({d + w, v});
}
}
return ans;
}
int solve(int x, int y, long long k) {
int ans = easy_solve(x, y, k);
vector<vector<long long>> dis(2);
dis[0] = distance(x);
dis[1] = distance(y);
vector<long long> both(n), single(n);
for (int i=0; i<n; i++) both[i] = max(dis[0][i], dis[1][i]);
for (int i=0; i<n; i++) single[i] = min(dis[0][i], dis[1][i]);
vector<int> o(n);
iota(o.begin(), o.end(), 0);
sort(o.begin(), o.end(), [&] (int i, int j) {return both[i] < both[j];});
vector<bool> bo(n), uni(n);
vector<int> path;
auto dfs = [&] (auto dfs, int u, int p) -> bool {
path.push_back(u);
if (u == y) return true;
for (auto [v, w]: adj[u]) {
if (v == p) continue;
if (dfs(dfs, v, u)) return true;
}
path.pop_back();
return false;
};
dfs(dfs, x, -1);
for (int u: path) uni[u] = 1;
// long long ocost = 0;
for (int u: o) {
bo[u] = true;
uni[u] = false;
// ocost += both[u];
long long cost = 0;
vector<bool> vis(n);
using pii = tuple<int, long long, int>;
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i=0; i<n; i++) {
if (bo[i]) {
pq.push({-1, both[i], i});
}
}
int res = 0;
while (pq.size()) {
auto [ty, s, u] = pq.top(); pq.pop();
if (vis[u]) continue;
if (cost + s > k) break;
vis[u] = true;
cost += s;
if (bo[u]) {
res += 2;
}else{
res += 1;
}
for (auto [v, w]: adj[u]) {
if (vis[v]) continue;
if (bo[v]) continue;
pq.push({uni[v] ? 0 : +1, single[v], v});
}
}
if (vis[x] && vis[y]) {
ans = max(ans, res);
}
}
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);
}
