#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, long long>>> 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]});
}
vector<long long> dX(N, -1), dY(N, -1);
vector<int> parent(N, -1);
// 树上 BFS，寻找各点到 X 和 Y 的距离，并记录指向 X 侧的父节点
auto bfs = [&](int start, vector<long long>& dist, bool record_parent) {
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;
long long w = edge.second;
if (dist[v] == -1) {
dist[v] = dist[u] + w;
if (record_parent) parent[v] = u;
q.push(v);
}
}
}
};
bfs(X, dX, true);
bfs(Y, dY, false);
// Case 1: 假设 X 的覆盖集和 Y 的覆盖集不发生相交
vector<long long> all_d;
all_d.reserve(2 * N);
for (int i = 0; i < N; ++i) {
all_d.push_back(dX[i]);
all_d.push_back(dY[i]);
}
sort(all_d.begin(), all_d.end());
long long ans1 = 0;
long long sum_d = 0;
for (int i = 0; i < 2 * N; ++i) {
if (sum_d + all_d[i] <= K) {
sum_d += all_d[i];
ans1++;
} else {
break;
}
}
// Case 2: 假设 X 的覆盖集和 Y 的覆盖集有相交成分
// 追踪出路径 P
vector<bool> on_P(N, false);
vector<int> P;
int curr = Y;
while (curr != -1) {
on_P[curr] = true;
P.push_back(curr);
if (curr == X) break;
curr = parent[curr];
}
long long cost_P = 0;
for (int u : P) {
cost_P += min(dX[u], dY[u]); // 强制 P 上的所有点被较近的源激活以铺设连通枢纽（每点得 1 分）
}
long long ans2 = 0;
if (cost_P <= K) {
long long rem_K = K - cost_P;
long long base_score = P.size();
// 为各个游离在主路径以外的子树定根求归属
vector<int> root_p(N, -1);
queue<int> q;
for (int u : P) {
root_p[u] = u;
q.push(u);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto& edge : adj[u]) {
int v = edge.first;
if (root_p[v] == -1 && !on_P[v]) {
root_p[v] = root_p[u];
q.push(v);
}
}
}
vector<long long> ones;
struct Two {
long long cost;
long long A;
bool operator<(const Two& o) const { return cost < o.cost; }
};
vector<Two> twos;
for (int i = 0; i < N; ++i) {
if (on_P[i]) {
// 如果在 P 上，只剩下唯一的一个边缘二次进阶开销项
ones.push_back(abs(dX[i] - dY[i]));
} else {
int p = root_p[i];
long long A = min(dX[i], dY[i]);
long long B = abs(dX[p] - dY[p]);
if (A <= B) {
ones.push_back(A);
ones.push_back(B);
} else {
twos.push_back({A + B, A});
}
}
}
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;
// 对于无法买下整个 "2分打包件" 但可以退而求其次买下其首分 A 的预处理
vector<long long> min_break(twos.size() + 1, 2e18);
for (int i = (int)twos.size() - 1; i >= 0; --i) {
min_break[i] = min(min_break[i + 1], twos[i].A);
}
// 穷举使用了多少个1分包裹，二分搭配尽可能多的2分包裹
for (size_t c = 0; c <= ones.size(); ++c) {
if (P1[c] > rem_K) break;
long long budget_left = rem_K - P1[c];
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_score = base_score + c + 2LL * c2;
ans2 = max(ans2, current_score);
// 残羹剩饭是否足以再买一个散装的 "1分" 物品
if (c2 < (int)twos.size()) {
if (budget_left - P2[c2] >= min_break[c2]) {
ans2 = max(ans2, current_score + 1);
}
}
}
}
return max(ans1, ans2); // 综合取两种局面的理论巅峰
}
