#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
using ll = long long;
using pll = pair<ll, int>;
const ll inf = 1e18;
vector<vector<pair<int, int>>> adj;
vector<vector<ll>> dist;
vector<vector<int>> pai;
void init( int n ){
adj.clear(); adj.resize(n);
dist.clear(); dist.resize( 2, vector<ll>(n));
pai.clear(); pai.resize( 2, vector<int>(n));
}
void dfs( int cur, int last, int t ){
pai[t][cur] = last;
for( auto [viz, d] : adj[cur] ) if( viz != last ){
dist[t][viz] = dist[t][cur] + d;
dfs( viz, cur, t );
}
}
int max_score(int n, int x, int y, long long k, vector<int> a, vector<int> b, vector<int> c ) {
init(n);
int m = a.size();
for( int i = 0; i < m; i++ ){
adj[a[i]].push_back({ b[i], c[i] });
adj[b[i]].push_back({ a[i], c[i] });
}
dfs( x, x, 0 );
dfs( y, y, 1 );
int resp = 0;
ll suml = 0;
for( int l = x; l >= 0; l-- ){
suml += dist[0][l];
ll sumr = 0;
for( int r = y; r < n; r++ ){
sumr += dist[1][r];
int px = x + 1, py = y - 1;
ll sum = 0;
while( true ){
ll cx, cy;
if( px <= py ){
cx = dist[0][px];
cy = dist[1][py];
}
else{
cx = dist[0][px] - dist[1][px];
cy = dist[1][py] - dist[0][py];
}
if( cx < l ) cx = inf;
if( cy > r ) cy = inf;
if( k < min( cx, cy ) + suml + sumr + sum ){
resp = max( resp, px - l + r - py );
break;
}
if( cx <= cy ){
sum += cx;
px++;
}
else{
sum += cy;
py--;
}
}
}
}
return resp;
}
