#include "closing.h"
#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
using llong = long long;
const llong INF = 4e18;
struct Edge {
int u, v, w;
int opp(int x) const {
return x == u ? v : u;
}
};
vector<Edge> edges;
vector< vector<int> > tree;
llong K;
void dfs(int u, int p, llong t, vector<llong>& closing_times) {
if (t > K)
return;
closing_times[u] = t;
for (int eid : tree[u]) {
int v = edges[eid].opp(u);
if (v == p) continue;
int w = edges[eid].w;
dfs(v, u, t + w, closing_times);
}
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
::K = K;
// cerr << "K: " << K << endl;
tree = vector< vector<int> >(N);
for (int j = 0; j < N-1; j++) {
int u = U[j], v = V[j], w = W[j];
int eid = edges.size();
edges.push_back({u, v, w});
tree[u].push_back(eid);
tree[v].push_back(eid);
}
// subtask1
vector<llong> closing_timesX(N, INF);
dfs(X, -1, 0, closing_timesX);
vector<llong> closing_timesY(N, INF);
dfs(Y, -1, 0, closing_timesY);
priority_queue<llong> pq;
llong sum = 0;
for (int u = 0; u < N; ++u) {
llong t = min(closing_timesX[u], closing_timesY[u]);
if (t <= K) {
pq.push(t);
sum += t;
}
}
while (sum > K) {
llong t = pq.top(); pq.pop();
sum -= t;
}
return pq.size();
}
