#include "bits/extc++.h"
using namespace std;
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t;
((cerr << " | " << u), ...);
cerr << endl;
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
<< ": "; \
dbgh(__VA_ARGS__)
#else
#define cerr \
if (false) \
cerr
#define dbg(...)
#endif
using ll = long long;
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
out << "[";
for (int i = 0; i < sz(arr); i++) {
if (i) {
out << ", ";
}
out << arr[i];
}
return out << "]";
}
template <typename Cb>
struct Cmp {
Cb cb;
Cmp(Cb cb) : cb(cb) {}
template <typename T>
bool operator()(const T& a, const T& b) const {
return cb(a) < cb(b);
}
};
vector<vector<pair<int, long>>> edges_to_adj(
int n,
const vector<tuple<int, int, long>>& edges) {
vector<vector<pair<int, long>>> graph(n);
for (auto& [u, v, w] : edges) {
graph[u].emplace_back(v, w);
graph[v].emplace_back(u, w);
}
return graph;
}
struct DistDFS {
vector<long> dist;
vector<vector<pair<int, long>>> graph;
DistDFS(int root, int n, const vector<tuple<int, int, long>>& edges)
: dist(n), graph(edges_to_adj(n, edges)) {
dfs(root, -1, 0);
}
void dfs(int u, int p, long d) {
dist[u] = d;
for (auto& [v, w] : graph[u]) {
if (v == p) {
continue;
}
dfs(v, u, d + w);
}
}
};
struct PathDFS {
int n;
vector<int> path;
vector<char> on_path;
vector<vector<int>> path_subs;
vector<vector<pair<int, long>>> graph;
PathDFS(int u0, int u1, int n, const vector<tuple<int, int, long>>& edges)
: n(n), on_path(n), graph(edges_to_adj(n, edges)) {
pdfs(u0, -1, u1);
for (auto& a : path) {
on_path[a] = true;
}
for (auto& a : path) {
path_subs.emplace_back();
dfs(a, -1, path_subs.back());
}
}
vector<int> st;
void pdfs(int u, int p, int targ) {
st.push_back(u);
if (u == targ) {
path = st;
}
for (auto& [v, _w] : graph[u]) {
if (v == p) {
continue;
}
pdfs(v, u, targ);
}
st.pop_back();
}
void dfs(int u, int p, vector<int>& out) {
out.push_back(u);
for (auto& [v, _w] : graph[u]) {
if (v == p || on_path[v]) {
continue;
}
dfs(v, u, out);
}
}
};
struct DS {
multiset<long> v[2];
void insert(int ind, long x) {
dbg("+", ind, x);
v[ind].insert(x);
}
void erase(int ind, long x) {
dbg("-", ind, x);
assert(v[ind].find(x) != v[ind].end());
v[ind].erase(v[ind].find(x));
}
int query(long kv) {
vector<long> ps0 {0}, ps1 {0};
for (auto& a : v[0]) {
ps0.push_back(ps0.back() + a);
}
for (auto& a : v[1]) {
ps1.push_back(ps1.back() + a);
}
int ans = -1e9;
for (int i = 0, j = sz(ps1) - 1; i < sz(ps0); i++) {
for (; j >= 0 && ps0[i] + ps1[j] > kv; j--)
;
if (j < 0) {
break;
}
ans = max(ans, 2 * i + j);
}
return ans;
}
};
int solve_disjoint(long kv,
const vector<long>& dist0,
const vector<long>& dist1) {
vector<long> dists;
dists.insert(dists.end(), begin(dist0), end(dist0));
dists.insert(dists.end(), begin(dist1), end(dist1));
sort(begin(dists), end(dists));
long sum = 0;
int i;
for (i = 0; i < sz(dists); i++) {
sum += dists[i];
if (sum > kv) {
break;
}
}
return i;
}
int solve(int n, int u0, int u1, long kv, vector<tuple<int, int, long>> edges) {
auto dist0 = DistDFS(u0, n, edges).dist, dist1 = DistDFS(u1, n, edges).dist;
auto path_dfs = PathDFS(u0, u1, n, edges);
auto path = path_dfs.path_subs;
int m = sz(path);
vector<long> cost1(n), cost2(n), delta(n);
for (int i = 0; i < n; i++) {
cost1[i] = min(dist0[i], dist1[i]);
cost2[i] = max(dist0[i], dist1[i]);
delta[i] = cost2[i] - cost1[i];
}
map<long, vector<int>> mp;
for (int i = 0; i < m; i++) {
mp[delta[path[i][0]]].push_back(i);
}
DS ds;
int ans = solve_disjoint(kv, dist0, dist1);
dbg(ans);
int ans_add = 0;
long min_cost = 0;
for (auto& a : path_dfs.path) {
ans_add++;
min_cost += cost1[a];
}
auto move_vals = [&](vector<int> nodes, bool undo) -> void {
sort(begin(nodes), end(nodes),
Cmp([&](int u) -> long { return cost1[u]; }));
for (auto& u : nodes) {
if (path_dfs.on_path[u]) {
ans_add++;
min_cost += delta[u];
} else {
ds.erase(1, cost1[u]);
ds.insert(0, cost2[u]);
}
ans = max(ans, ans_add + ds.query(kv - min_cost));
dbg(ans, ans_add, min_cost);
}
if (!undo) {
return;
}
for (auto& u : nodes) {
if (path_dfs.on_path[u]) {
ans_add--;
min_cost -= delta[u];
} else {
ds.insert(1, cost1[u]);
ds.erase(0, cost2[u]);
}
}
};
for (int i = 0; i < n; i++) {
if (path_dfs.on_path[i]) {
continue;
}
ds.insert(1, cost1[i]);
}
for (auto& [_k, vals] : mp) {
dbg(vals);
if (sz(vals) == 1) {
move_vals(path[vals[0]], false);
continue;
}
assert(sz(vals) == 2);
dbg(ans_add, min_cost);
move_vals(path[vals[0]], true);
dbg(ans_add, min_cost);
move_vals(path[vals[1]], false);
move_vals(path[vals[0]], false);
}
return ans;
}
int max_score(int n,
int u0,
int u1,
ll kv,
vector<int> edges_u,
vector<int> edges_v,
vector<int> edges_w) {
vector<tuple<int, int, long>> edges;
for (int i = 0; i < n - 1; i++) {
edges.emplace_back(edges_u[i], edges_v[i], edges_w[i]);
}
return solve(n, u0, u1, kv, edges);
}
