#include "closing.h"
#include <vector>
#include <queue>
#include <iostream>
#define ll long long
#define vi vector<ll>
#define pb push_back
#define ii pair<ll, ll>
#define inf 1'000'000'000'000'000'000
using namespace std;
vector<ii> graf[200005];
vi dis1, dis2;
void dfs(ll u, vi& dis, ll p = -1)
{
for (auto [v, w]:graf[u])
{
if (v == p) continue;
dis[v] = dis[u]+w;
dfs(v, dis, u);
}
}
ll sol1(ll n, ll x, ll y, ll k)
{
priority_queue<ll, vi, greater<ll>> pq;
for (ll i = 0; i < n; i++)
pq.push(dis2[i]);
ll tk = 0;
ll rez = 0;
while (pq.size() && tk+pq.top() <= k)
{
tk+=pq.top();
pq.pop();
rez++;
}
return rez;
}
// ll sol2()
// {
// }
int max_score(int n, int x, int y, long long k, vector<int> U, vector<int> V, vector<int> W)
{
for (ll i = 0; i < n; i++)
graf[i].clear();
dis1.clear();
dis2.clear();
dis1 = dis2 = vi(n, 0);
for (ll i = 0; i < n-1; i++)
{
graf[U[i]].pb({V[i], W[i]});
graf[V[i]].pb({U[i], W[i]});
}
dfs(x, dis1);
dfs(y, dis2);
for (ll i = 0; i < n; i++)
if (dis1[i] < dis2[i])
swap(dis1[i], dis2[i]);
ll rez = sol1(n, x, y, k);
return rez;
}
