// CF template, version 3.0
#include <bits/stdc++.h>
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
//#define int long long int
template <typename T, typename I>
struct segtree {
int n;
vector<T> tree;
vector<I> initial;
T id;
segtree(int i_n, vector<I> i_initial, T i_id): n(i_n), initial(i_initial), id(i_id) {
tree.resize(4 * n);
}
T conquer(T left, T right) {
// write your conquer function
}
T value(I inp) {
// write your value function
}
void build(int v, int l, int r) {
if (l == r) tree[v] = value(initial[l]);
else {
int middle = (l + r) / 2;
build(2 * v, l, middle);
build(2 * v + 1, middle + 1, r);
tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
}
}
void upd(int v, int l, int r, int i, I x) {
if (l == r) tree[v] = value(x);
else {
int middle = (l + r) / 2;
if (middle >= i) upd(2 * v, l, middle, i, x);
else upd(2 * v + 1, middle + 1, r, i, x);
tree[v] = conquer(tree[2 * v], tree[2 * v + 1]);
}
}
T query(int v, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[v];
else if (r < ql || qr < l) return id;
int middle = (l + r) / 2;
T left = query(2 * v, l, middle, ql, qr);
T right = query(2 * v + 1, middle + 1, r, ql, qr);
return conquer(left, right);
}
};
// vector<int>
vector<vector<pair<int, int>>> adjList;
vector<long long> fromX;
vector<long long> fromY;
void dfs(int v, int p, long long d, int which) {
if (which) fromY[v] = d;
else fromX[v] = d;
for (auto pa: adjList[v]) {
int con = pa.first;
long long w = pa.second;
if (con == p) continue;
dfs(con, v, d + w, which);
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
adjList.clear();
adjList.resize(N);
fromX.clear();
fromX.resize(N);
fromY.clear();
fromY.resize(N);
forto(N - 1, i) {
int a = U[i];
int b = V[i];
int w = W[i];
adjList[a].push_back({b, w});
adjList[b].push_back({a, w});
}
dfs(X, -1, 0ll, 0);
dfs(Y, -1, 0ll, 1);
if (fromY[X] > 2 * K) {
vector<long long> paths;
forto(N, i) {
paths.push_back(min(fromX[i], fromY[i]));
}
sortl(paths);
int ans = 0;
long long sum = 0;
forto(N, i) {
if (sum + paths[i] > K) break;
sum += paths[i];
ans++;
}
return ans;
} else {
// assumption: path
// case 1: everything in between contributes twice.
long long C = fromX[Y]; // = fromY[X]
long long sum1 = 0ll;
int ans = 0;
int ans1 = 0;
vector<long long> far;
forto(N, i) {
int val = max(fromX[i], fromY[i]);
if (val < C) sum1 += val, ans1 += 2;
else far.push_back(min(fromX[i], fromY[i]));
}
int s = far.size();
if (sum1 <= K) {
sortl(far);
long long left = K - sum1;
ans = max(ans, ans1);
long long farsum = 0;
forto(s, i) {
farsum += far[i];
if (farsum > left) break;
long long extra = (left - farsum) / C;
int extraint = extra > (long long) (i + 1)? i + 1: (int) extra;
ans = max(ans, ans1 + (i + 1) + extraint);
}
}
vector<pair<long long, int>> middle;
forto(N, i) {
int val = max(fromX[i], fromY[i]);
if (val < C) middle.push_back({fromX[i], i});
}
sortl(middle);
int midsz = middle.size();
int ans2 = 0;
far.push_back(0);
s++;
sortl(far);
long long sum2 = 0ll;
forto(s, i) {
sum2 += far[i];
if (sum2 > K) break;
long long left = K - sum2;
forto(midsz + 1, l) {
long long taken = 0ll;
for (int r = l; r <= midsz; r++) {
if (r != midsz) taken += max(middle[r].first, fromY[middle[r].second]);
if (taken > left) break;
vector<long long> once;
forto(l, j) once.push_back(min(middle[j].first, fromY[middle[j].second]));
for (int j = r + 1; j < midsz; j++) once.push_back(min(middle[j].first, fromY[middle[j].second]));
sortl(once);
long long remain = left - taken;
int o = once.size();
int here = 0;
forto(o, i) {
if (remain < once[i]) break;
here++;
remain -= once[i];
}
ans2 = max(ans2, (i + 1) + 2 * (r == midsz? r - l: r - l + 1) + here - 1);
if (ans2 == 4) out(l), out(r);
}
}
}
ans = max(ans, ans2);
return ans;
}
}
