#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(ll n, ll x, ll y, ll k)
{
priority_queue<ii, vector<ii>, greater<ii>> pq;
int tk = 0;
int rez = 0;
vi dod(n);
for (int i = 0; i < n; i++)
{
if (dis1[i]+dis2[i] == dis1[x])
{
rez++;
dod[i] = 1;
// cout << "dd " << i << "\n";
tk += dis2[i];
pq.push({dis1[i]-dis2[i], i});
}
else
pq.push({dis2[i], i});
}
if (tk > k)
return 0;
while (pq.size() && tk+pq.top().first <= k)
{
auto [d, u] = pq.top();
// cout << "dd1 " << u << "\n";
// cout << tk << "\n";
pq.pop();
tk+=d;
if (!dod[u])
pq.push({dis1[u]-dis2[u], u});
dod[u] = 1;
rez++;
}
// cout << "-> " <<rez << "\n";
return rez;
}
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);
rez = max(rez, sol2(n, x, y, k));
return rez;
}
