#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++){
vector<pair<ll,pair<ll,ll>>> ss;
stack<pair<ll,pair<ll,ll>>> s1,st;
sum = 0;
ll ans1 = 2 * max(1, x - l + 1),sum1 = 0;
for(int i = 0; i < l; i++){
ss.pb({dis[i], {0, i}});
// sum1 += dis[i];
}
for(int i = y + 1; i < n; i++){
ss.pb({dis[i], {0, i}});
// sum1 += dis[i];
}
for(int i = 0; i < min(x, l); i++){
ss.pb({dis1[i], {1, i}});
// sum1 += dis1[i];
}
for(int i = max(l, x) + 1; i < n; i++){
if(i <= y){
ans1++;
sum += dis[i];
}
// sum1 += dis1[i];
ss.pb({dis1[i], {1, i}});
}
for(int i = x; i < l; i++){
ans1++;
sum += dis1[i];
}
for(int i = l; i <= max(l, x); i++) sum += max(dis[i], dis1[i]);
if(sum > K) continue;
ll idx = 0;
sort(ss.begin(), ss.end());
vector<vector<bool>> vis(n, vector<bool>(2, false));
ll curr = 0;
for(int i = 0; i < ss.size(); i++){
if(sum + sum1 + ss[i].ff <= K){
sum1 += ss[i].ff;
vis[ss[i].sd.sd][ss[i].sd.ff] = true;
st.push(ss[i]);
}
else{
idx = i;
break;
}
}
if(ss.size()) for(int i = ss.size() - 1; i >= idx; i--){
s1.push(ss[i]);
}
// while(sum + sum1 > K){
// auto it = ss.end(); --it;
// s1.push(*it);
// sum1 -= (*it).ff;
// ss.erase(it);
// }
ans = max(ans, ans1 + (ll)st.size());
for(int r = max(l, x) + 1; r < n; r++){
// auto it = s.find({dis[r], 0}),it1 = s.find({dis1[r], 1});
if(vis[r][0]){
sum1 -= dis[r];
curr++;
vis[r][0] = false;
// s.erase(it);
}
if(vis[r][1]){
sum1 -= dis1[r];
curr++;
vis[r][1] = false;
// s.erase(it1);
}
if(r <= y){
sum -= dis[r];
ans1--;
}
ans1 += 2;
sum += max(dis[r], dis1[r]);
if(sum > K) break;
while(sum + sum1 > K){
pair<ll,pair<ll,ll>> it2 = st.top();
st.pop();
if(!vis[it2.sd.sd][it2.sd.ff]){
curr--;
continue;
}
vis[it2.sd.sd][it2.sd.ff] = false;
s1.push(it2);
sum1 -= it2.ff;
// s.erase(it2);
}
while(s1.size()){
auto it2 = s1.top();
if(it2.ff + sum1 + sum > K) break;
sum1 += it2.ff;
st.push(it2);
vis[it2.sd.sd][it2.sd.ff] = true;
s1.pop();
}
ans = max(ans, ans1 + (ll)st.size() - curr);
}
}
for(int i = 0; i < n; i++) v[i].clear();
// cout << "aa" << endl;
return ans;
}
//1
//6 0 3 10
//5 3 5
//3 1 2
//1 2 1
//2 0 3
//0 4 7
