#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
vector<ll> distx, disty;
vector<vector<pair<ll,int>>> adj;
void get_dist(vector<ll>& dist, int u, int p = -1){
for(auto& [w, v]:adj[u]) if (v != p){
dist[v] = dist[u] + w;
get_dist(dist, v, u);
}
}
vector<ll> c1;
vector<pair<ll,ll>> c2;
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
adj.clear();
adj.resize(N);
for(int i=0;i<N-1;++i){
adj[U[i]].push_back({W[i], V[i]});
adj[V[i]].push_back({W[i], U[i]});
}
distx.resize(N); disty.resize(N);
distx[X] = 0;
disty[Y] = 0;
get_dist(distx, X);
get_dist(disty, Y);
// solve the first subtask
int ans = 0;
vector<ll> dists;
for(int i=0;i<N;++i) dists.push_back(min(distx[i], disty[i]));
sort(dists.begin(), dists.end());
ll kk = K;
for(auto&d:dists){
if (kk < d) break;
ans += 1;
kk -= d;
}
// now time to try and get a better answer using greed approach
kk = K;
ll D = distx[Y];
vector<bool> is_path(N, 0);
for(int i=0;i<N;++i){
if (distx[i] + disty[i] == D){
// this is a critical node
if (distx[i] > disty[i]){
// far from x, connect to y
kk -= disty[i];
} else {
kk -= distx[i];
}
is_path[i] = 1;
}
} // visit all the good nodes once
if (kk < 0) return ans;
// now maintain the caches
c1.clear(); c2.clear();
for(int i=0;i<N;++i){
ll dif = abs(distx[i]-disty[i]);
if(is_path[i]){
c1.push_back(0);
c1.push_back(dif);
}
else {
ll dst = min(distx[i], disty[i]);
if (dst <= dif) {
c1.push_back(dst);
c1.push_back(dif);
}
else {
c2.push_back({dst+dif, dst});
}
}
}
sort(c1.begin(), c1.end());
sort(c2.begin(), c2.end());
// next we compute suffix minimums
vector<ll> suf_min(c2.size()+1, INF);
for(int i=c2.size()-1;i>=0;--i){
suf_min[i] = min(suf_min[i+1], c2[i].second);
}
// for twos taken there are 3 cases:
// block of twos taken
// block of 2s, 1, 2
// block of 2s, suffix min.
// case 1: block of twos
ll taken = 0;
int numones = 0;
for(int i=0;i<c2.size();++i) {
taken += c2[i].first;
}
for(int numtwos = c2.size();numtwos >= 0; numtwos--){
if (taken > kk){
taken -= c2[numtwos-1].first;
continue;
}
// add ones
while (numones < c1.size() && taken + c1[numones] <= kk){
taken += c1[numones++];
}
ans = max(ans, numones + 2*numtwos);
}
// case 2: block of twos and a suffix minimum
taken = 0;
numones = 0;
for(int i=0;i<c2.size();++i) {
taken += c2[i].first;
}
taken += suf_min[c2.size()];
for(int numtwos = c2.size();numtwos >= 0; numtwos--){
if (taken > kk){
if (numtwos == 0){
break;
}
taken -= suf_min[numtwos];
taken -= c2[numtwos-1].first;
taken += suf_min[numtwos - 1];
continue;
}
// add ones
while (numones < c1.size() && taken + c1[numones] <= kk){
taken += c1[numones++];
}
ans = max(ans, numones + 2*numtwos + 1);
}
if (c2.size() < 2) return ans;
taken = 0;
numones = 0;
for(int i=0;i<c2.size()-2;++i){
taken += c2[i].first;
}
taken += c2[c2.size()-2].second;
taken += c2[c2.size()-1].first;
// case 3: block of twos, one, two
for(int numtwos = c2.size()-2;numtwos >= 0; numtwos--){
if (taken > kk){
if (numtwos == 0) break;
taken -= c2[numtwos-1].first;
taken -= c2[numtwos].second;
taken -= c2[numtwos+1].first;
taken += c2[numtwos-1].second;
taken += c2[numtwos].first;
continue;
}
// add ones
while (numones < c1.size() && taken + c1[numones] <= kk){
taken += c1[numones++];
}
ans = max(ans, numones + 2*numtwos + 3);
}
return ans;
}
