#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct Data{
int n;
int convenience_score = 2;
vector<vector<pair<int, int>>> adj_list;
long long t_w = 0;
long long closing_time_sum = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> queue;
vector<int> closing_time;
};
void traversal(vector<int> &cl_time, long long &cl_sum, long long K, long long total_weight, vector<vector<pair<int, int>>> &adj_list, int &convenience_score, int city, int prev_city, int other_city)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> queue;
int prev = city;
if (adj_list[city].empty())
{
return;
}
for (auto u : adj_list[city])
{
queue.push(u);
}
while (!queue.empty())
{
pair<int, int> v = queue.top();
queue.pop();
if (v.second == other_city)
{
return;
}
if (v.second == prev_city)
{
continue;
}
long long new_weight = total_weight + v.first;
cl_sum += new_weight;
if (cl_sum <= K && cl_time[v.second] == 0)
{
cl_time[v.second] = v.first;
convenience_score++;
traversal(cl_time, cl_sum, K, new_weight, adj_list, convenience_score, v.second, prev, other_city);
}
else
{
cl_sum -= new_weight;
if (cl_time[v.second])
{
if (new_weight <= cl_time[v.second])
{
convenience_score++;
}
else
{
int surplus = v.first - cl_time[v.second];
cl_sum += surplus;
cl_time[v.second] = v.first;
convenience_score++;
}
}
}
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
Data data;
data.adj_list.resize(N);
data.closing_time.resize(N);
for (int i = 0; i < N; i++){
data.adj_list[U[i]].push_back({W[i], V[i]});
data.adj_list[V[i]].push_back({W[i], U[i]});
}
if (X != Y){
traversal(data.closing_time, data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, X, X, Y);
traversal(data.closing_time,data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, Y, Y, X);
}
else if (X == Y){
data.convenience_score -= 1;
traversal(data.closing_time,data.closing_time_sum, K, data.t_w, data.adj_list, data.convenience_score, X, X, Y);
}
return data.convenience_score;
}
