#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define ll long long
#define pll pair<ll, ll>
ll n;
vector<pair<ll, ll> > graph[N];
ll dist[N][2];
void dfs(ll startIndex, ll ind, ll p = -1, ll dep = 0) {
dist[startIndex][ind] = dep;
for(auto [el, w] : graph[startIndex]) {
if(el == p) continue;
dfs(el, ind, startIndex, dep + w);
}
}
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; i++ ) {
graph[i].clear();
}
for(int i = 0; i < n - 1; i++) {
graph[U[i]].push_back({V[i], W[i]});
graph[V[i]].push_back({U[i], W[i]});
}
dfs(X, 0);
dfs(Y, 1);
for(int i= 0; i < n; i++) {
//cout<<i<<" "<<dist[i][0]<<" "<<dist[i][1]<<endl;
}
priority_queue<pll, vector<pll>, greater<pll> > pq;
for(int i = 0; i < n; i++) {
if(dist[i][0] < dist[i][1]) {
pq.push({dist[i][0], i});
dist[i][1] -= dist[i][0];
dist[i][0] = -1;
} else {
pq.push({dist[i][1], i});
dist[i][0] -= dist[i][1];
dist[i][1] = -1;
}
}
ll curr = 0;
ll ans = 0;
while(!pq.empty()) {
auto [dista, node] = pq.top();
pq.pop();
//cout<<" = > "<<dista<<" "<<node<<endl;
if(curr + dista <= K) {
ans += 1;
curr += dista;
if(dist[node][0] != -1) {
pq.push({dist[node][0], node});
dist[node][0] = -1;
}
if(dist[node][1] != -1) {
pq.push({dist[node][1], node});
dist[node][1] = -1;
}
} else break;
}
return ans;
}
