#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
ll dp[2][N] , a[N] , b[N] , c[N] , pr[N];
vector<ll> g[N];
int solve(ll n , ll x , ll y , ll k){
for(ll i = 1; i <= n; i++) g[i].clear();
for(ll i = 1; i < n; i++){
g[a[i]].push_back(i);
g[b[i]].push_back(i);
}
if(x > y) swap(x,y);
for(ll i = 0; i < 2; i++){
for(ll j = 1; j <= n; j++){
dp[i][j] = inf;
}
set<pair<ll,ll>> st;
if(i == 0) dp[i][x] = 0 , st.insert({0,x});
else dp[i][y] = 0 , st.insert({0,y});
while(st.size()){
ll v = st.begin()->S;
st.erase(st.begin());
for(ll k : g[v]){
ll to = (a[k]^b[k]^v);
if(dp[i][to] > dp[i][v] + c[k]){
st.erase({dp[i][to],to});
dp[i][to] = dp[i][v] + c[k];
st.insert({dp[i][to],to});
}
}
}
}
int cur = 0;
for(int l = 1; l <= n; l++){
for(int r = l; r <= n; r++){
if(l <= x && x <= r){
for(int i = 1; i <= n; i++) c[i] = 0;
for(int i = l; i <= r; i++) c[i] = dp[0][i];
for(int i = r+1; i <= y; i++) if(c[i] < dp[1][i]) c[i] = dp[1][i];
ll bar = k;
vector<pair<ll,ll>> vec;
for(int i = 1; i <= n; i++) {
bar -= c[i];
vec.push_back({max(0ll,dp[1][i]-c[i]),i});
}
sort(all(vec));
for(int i = 0; i < vec.size(); i++){
if(vec[i].F <= bar){
bar -= vec[i].F;
c[vec[i].S] += vec[i].F;
}
}
int ans = 1;
for(int i = x+1; i <= n; i++){
if(c[i] >= dp[0][i]) ans++;
else break;
}
for(int i = x-1; i >= 1; i--){
if(c[i] >= dp[0][i]) ans++;
else break;
}
ans++;
for(int i = y+1; i <= n; i++){
if(c[i] >= dp[1][i]) ans++;
else break;
}
for(int i = y-1; i >= 1; i--){
if(c[i] >= dp[1][i]) ans++;
else break;
}
cur = max(cur , ans);
}
}
}
return cur;
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
for(int i = 0; i < N; i++){
a[i+1] = U[i]+1;
b[i+1] = V[i]+1;
c[i+1] = W[i];
}
return solve(N , X+1 , Y+1 , K);
}
// int main()
// {
//
// int Q;
// assert(1 == scanf("%d", &Q));
//
// std::vector<int> N(Q), X(Q), Y(Q);
// std::vector<long long> K(Q);
// std::vector<std::vector<int>> U(Q), V(Q), W(Q);
//
// for (int q = 0; q < Q; q++)
// {
// assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
//
// U[q].resize(N[q] - 1);
// V[q].resize(N[q] - 1);
// W[q].resize(N[q] - 1);
// for (int i = 0; i < N[q] - 1; ++i)
// {
// assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
// }
// }
// fclose(stdin);
//
// std::vector<int> result(Q);
// for (int q = 0; q < Q; q++)
// {
// result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
// }
//
// for (int q = 0; q < Q; q++)
// {
// printf("%d\n", result[q]);
// }
// fclose(stdout);
//
// return 0;
// }
