#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
long long max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < N - 1; ++i) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
// 计算到 X 和 Y 的距离
vector<long long> dX(N, -1), dY(N, -1);
auto bfs = [&](int start, vector<long long>& dist) {
queue<int> q;
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (dist[v] == -1) {
dist[v] = dist[u] + w;
q.push(v);
}
}
}
};
bfs(X, dX);
bfs(Y, dY);
// 找到 X 到 Y 的路径 P
vector<int> parent(N, -1);
queue<int> q;
q.push(X);
vector<bool> vis(N, false);
vis[X] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == Y) break;
for (auto& edge : adj[u]) {
int v = edge.first;
if (!vis[v]) {
vis[v] = true;
parent[v] = u;
q.push(v);
}
}
}
vector<bool> on_path(N, false);
int curr = Y;
while (curr != -1) {
on_path[curr] = true;
curr = parent[curr];
}
// 划分各子树并判定归属源
vector<int> root_p(N, -1);
q = queue<int>();
for (int i = 0; i < N; ++i) {
if (on_path[i]) {
root_p[i] = i;
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& edge : adj[u]) {
int v = edge.first;
if (root_p[v] == -1) {
root_p[v] = root_p[u];
q.push(v);
}
}
}
vector<long long> ones;
struct TwoItem {
long long cost;
long long brk;
bool operator<(const TwoItem& other) const {
return cost < other.cost;
}
};
vector<TwoItem> twos;
// 筛选物品逻辑构建
for (int i = 0; i < N; ++i) {
int p = root_p[i];
long long delta = abs(dX[p] - dY[p]);
long long v = min(dX[i], dY[i]);
if (v < delta) {
ones.push_back(v);
ones.push_back(delta);
} else {
twos.push_back({v + delta, v});
}
}
sort(ones.begin(), ones.end());
sort(twos.begin(), twos.end());
vector<long long> P1(ones.size() + 1, 0);
for (size_t i = 0; i < ones.size(); ++i) {
P1[i + 1] = P1[i] + ones[i];
}
vector<long long> P2(twos.size() + 1, 0);
for (size_t i = 0; i < twos.size(); ++i) {
P2[i + 1] = P2[i] + twos[i].cost;
}
vector<long long> min_break(twos.size() + 1, 2e18); // fallback
for (int i = (int)twos.size() - 1; i >= 0; --i) {
min_break[i] = min(min_break[i + 1], twos[i].brk);
}
long long max_pts = 0;
for (size_t c = 0; c <= ones.size(); ++c) {
long long budget_left = K - P1[c];
if (budget_left < 0) break;
// 查找在剩余预算内能买到多少2分包
int low = 0, high = twos.size(), c2 = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (P2[mid] <= budget_left) {
c2 = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
long long current_pts = c + 2LL * c2;
max_pts = max(max_pts, current_pts);
if (c2 < (int)twos.size()) {
long long budget_after_twos = budget_left - P2[c2];
if (budget_after_twos >= min_break[c2]) {
max_pts = max(max_pts, current_pts + 1);
}
}
}
return max_pts;
}
