#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 2e5;
struct edge {
int to, wei;
};
int ans;
int n, x, y, k;
vector<pii > g[1 + maxn];
int d[2][1 + maxn];
bool done[2][1 + maxn];
void dfs(int cur, int idx, int par) {
for(pii nei : g[cur]) {
if(nei.fi != par) {
d[idx][nei.fi] = d[idx][cur] + nei.se;
dfs(nei.fi, idx, cur);
}
}
}
struct item {
int val;
int pos;
int type;
bool operator < (const item & other) const {
return val > other.val;
}
};
int sum, cur_ans;
priority_queue<item> q;
void push_for(item cur) {
for(pii nei : g[cur.pos]) {
if(!done[cur.type][nei.fi]) {
q.push({d[cur.type][nei.fi], nei.fi, cur.type});
}
}
}
bool eval(item cur) {
if(cur.val > k - sum) {
return false;
}
sum += cur.val;
cur_ans++;
done[cur.type][cur.pos] = true;
push_for(cur);
return true;
}
void solve() {
dfs(x, 0, -1);
dfs(y, 1, -1);
q.push({0, x, 0});
q.push({0, y, 1});
sum = 0, cur_ans = 0;
while(!q.empty()) {
item cur = q.top();
q.pop();
bool res = eval(cur);
if(!res) {
break;
}
}
ans = cur_ans;
}
void reset() {
ans = 0;
for(int i = 1; i <= n; i++) {
g[i].clear();
d[0][i] = d[1][i] = 0;
done[0][i] = done[1][i] = false;
}
sum = 0, cur_ans = 0;
while(!q.empty()) {
q.pop();
}
//
}
signed max_score(signed N, signed X, signed Y, int K,
vector<signed> U, vector<signed> V, vector<signed> W) {
reset();
n = N, x = X, y = Y, k = K;
x++;
y++;
for(int i = 0; i < n - 1; i++) {
int a = U[i], b = V[i], c = W[i];
a++;
b++;
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
solve();
return ans;
}
