#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18L + 20;
namespace cardboard {
vector<pair<int, long long>> boxes;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
return boxes[p1.second].second - boxes[p1.first].second > boxes[p2.second].second - boxes[p2.first].second;
}
int solve(int N, long long K, vector<pair<long long, long long>> costs) {
vector<pair<long long, int>> order(N << 1);
for (int i = 0; i < N; i++) {
order[i << 1] = {costs[i].first << 1, i << 1};
order[i << 1 | 1] = {costs[i].second, i << 1 | 1};
}
sort(order.begin(), order.end());
vector<pair<int, int>> ids(N);
boxes.resize(N << 1);
for (int i = 0; i < (N << 1); i++) {
if (order[i].second & 1) {
boxes[i] = {2, order[i].first};
ids[order[i].second >> 1].second = i;
}
else {
boxes[i] = {1, order[i].first >> 1};
ids[order[i].second >> 1].first = i;
}
}
sort(ids.begin(), ids.end(), cmp);
vector<long long> cur_dp = {0};
for (int i = 0; i < N; i++) {
vector<long long> nxt_dp = cur_dp;
nxt_dp.resize((int)nxt_dp.size() + 2, inf);
for (int j = 0; j < (int)cur_dp.size(); j++) {
nxt_dp[j + 1] = min(nxt_dp[j + 1], cur_dp[j] + boxes[ids[i].first].second);
nxt_dp[j + 2] = min(nxt_dp[j + 2], cur_dp[j] + boxes[ids[i].second].second);
}
cur_dp.swap(nxt_dp);
}
for (int i = N * 2; i >= 0; i--) {
if (cur_dp[i] <= K) {
return i;
}
}
return 0;
}
}
namespace tree {
vector<vector<pair<int, int>>> adj;
void init(int N) {
adj.resize(N);
for (int i = 0; i < N; i++) {
adj[i].clear();
}
}
void add_edge(int u, int v, int w) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
void dfs(int u, int p, vector<long long> &dist) {
for (auto [v, w]: adj[u]) {
if (v != p) {
dist[v] = dist[u] + w;
dfs(v, u, dist);
}
}
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
tree::init(N);
for (int i = 0; i < N - 1; i++) {
tree::add_edge(U[i], V[i], W[i]);
}
vector<long long> distX(N), distY(N);
tree::dfs(X, -1, distX);
tree::dfs(Y, -1, distY);
vector<long long> dists(distX.begin(), distX.end());
dists.insert(dists.end(), distY.begin(), distY.end());
sort(dists.begin(), dists.end());
int res = 0;
long long sum = 0;
for (auto d: dists) {
if (sum + d <= K) {
sum += d;
res++;
}
else {
break;
}
}
int cnt = 0;
vector<pair<long long, long long>> costs(N);
for (int i = 0; i < N; i++) {
if (distX[i] + distY[i] == distX[Y]) {
cnt++;
K -= min(distX[i], distY[i]);
costs[i] = {max(distX[i], distY[i]) - min(distX[i], distY[i]), inf};
}
else {
costs[i] = {min(distX[i], distY[i]), max(distX[i], distY[i])};
}
}
if (K >= 0) {
res = max(res, cnt + cardboard::solve(N, K, costs));
}
return res;
}
