#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
const int mxN = 3e5 + 5;
ll n,dis[mxN],dis1[mxN],dis2[mxN];
vector<pair<ll,ll>> v[mxN];
vector<ll> vv;
void dfs(ll at, ll par, bool ok = false){
if(ok) vv.pb(at);
for(auto it : v[at]){
if(it.ff == par) continue;
dis[it.ff] = dis[at] + it.sd;
dfs(it.ff, at, ok);
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
n = N;
for(int i = 0; i < n - 1; i++){
v[U[i]].pb({V[i], W[i]});
v[V[i]].pb({U[i], W[i]});
}
ll root = 0;
for(int i = 0; i < n; i++) if(v[i].size() == 1){
root = i;
break;
}
dis[root] = 0;
vv.clear();
dfs(root, root, true);
int x,y;
for(int i = 0; i < n; i++){
if(vv[i] == X) x = i;
if(vv[i] == Y) y = i;
}
if(x > y) swap(x, y);
dis[X] = 0;
dfs(X, X);
for(int i = 0; i < n; i++) dis1[i] = dis[vv[i]];
dis[Y] = 0;
dfs(Y, Y);
for(int i = 0; i < n; i++) dis2[i] = dis[i];
for(int i = 0; i < n; i++) dis[i] = dis2[vv[i]];
ll sum = 0,ans = 0;
vector<ll> v2;
for(int i = 0; i < n; i++){
v2.pb(dis[i]);
v2.pb(dis1[i]);
}
sort(v2.begin(), v2.end());
for(auto it : v2){
sum += it;
if(sum > K) break;
ans++;
}
for(int l = 0; l <= y; l++){
for(int r = l; r < n; r++){
if(r < x) continue;
sum = 0;
vector<ll> v1;
ll ans1 = 2 * (r - l + 1);
for(int i = l; i <= r; i++) sum += max(dis[i], dis1[i]);
for(int i = x; i < l; i++){
ans1++;
sum += dis1[i];
}
for(int i = r + 1; i <= y; i++){
ans1++;
sum += dis[i];
}
if(sum > K) continue;
for(int i = 0; i < min(x, l); i++) v1.pb(dis1[i]);
for(int i = r + 1; i < n; i++) v1.pb(dis1[i]);
for(int i = 0; i < l; i++) v1.pb(dis[i]);
for(int i = max(r, y) + 1; i < n; i++) v1.pb(dis[i]);
sort(v1.begin(), v1.end());
for(auto it : v1){
sum += it;
if(sum > K) break;
ans1++;
}
ans = max(ans, ans1);
}
}
for(int i = 0; i < n; i++) v[i].clear();
return ans;
}
//1
//6 0 3 10
//5 3 5
//3 1 2
//1 2 1
//2 0 3
//0 4 7
