#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ll = long long;
using ii = pair<int, int>;
const ll INF = 1e18;
const int MAX_N = 2e5 + 9;
vector<ii> adj[MAX_N];
int n;
void dfs(int u, vector<ll> &dist, int p = -1, ll d = 0) {
dist[u] = d;
for (auto [v, w] : adj[u]) {
if (v != p) dfs(v, dist, u, d + w);
}
}
int non_overlaping(ll K, vector<ll> v) {
sort(all(v));
int ans = 0;
for (int i = 0; i < n; i++) {
if (v[i] <= K) {
K -= v[i];
ans++;
}
}
return ans;
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
n = N;
for (int i = 0; i < n; i++) adj[i].clear();
for (int i = 0; i < n - 1; i++) {
adj[U[i]].emplace_back(V[i], W[i]);
adj[V[i]].emplace_back(U[i], W[i]);
}
vector<ll> dist1(n), dist2(n);
dfs(X, dist1), dfs(Y, dist2);
vector<bool> path(n, false);
path[Y] = true;
int u = Y;
while (u != X) {
for (auto [v, w] : adj[u]) {
if (dist1[v] + w == dist1[u]) {
u = v;
break;
}
}
path[u] = true;
}
for (int i = 0; i < n; i++) {
if (dist1[i] > dist2[i]) swap(dist1[i], dist2[i]);
}
vector<ll> vec1;
vector<pair<ll, ll>> vec2;
ll remain = K;
int curr = 0;
for (int i = 0; i < n; i++) {
ll val1 = dist1[i];
ll val2 = dist2[i] - dist1[i];
if (path[i]) {
remain -= val1, curr++;
vec1.push_back(val2);
} else if (val1 <= val2) {
vec1.push_back(val1);
vec1.push_back(val2);
} else {
vec2.emplace_back(val1, val2);
}
}
sort(all(vec1));
sort(all(vec2), [](const pair<ll, ll> &a, const pair<ll, ll> &b) {
return a.first + a.second < b.first + b.second;
});
int S = sz(vec1);
vector<ll> prefSum(S + 1);
prefSum[0] = 0LL;
for (int i = 0; i < S; i++) {
prefSum[i + 1] = vec1[i];
prefSum[i + 1] += prefSum[i];
}
int M = sz(vec2);
vector<ll> prefMaxi(M + 1);
prefMaxi[0] = -INF;
for (int i = 0; i < M; i++) {
prefMaxi[i + 1] = vec2[i].second;
prefMaxi[i + 1] = max(prefMaxi[i + 1], prefMaxi[i]);
}
vector<ll> suffMini(M + 1);
suffMini[M] = INF;
for (int i = M - 1; i >= 0; i--) {
suffMini[i] = vec2[i].first;
suffMini[i] = min(suffMini[i], suffMini[i + 1]);
}
auto calc = [&](ll r) {
if (remain < 0) return int(-1e9);
auto it = upper_bound(all(prefSum), r);
return int(it - prefSum.begin());
};
for (int i = 0; i <= M; i++) {
remain -= vec2[i].first + vec2[i].second;
ans = max(ans, curr + calc(remain));
if (i < M) {
ans = max(ans, curr + 1 + calc(remain + suffMini[i + 1]));
ans = max(ans, curr - 1 + calc(remain - prefMaxi[i + 1]));
}
curr += 2;
}
return ans;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:108:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
108 | ans = max(ans, curr + calc(remain));
| ^~~
| abs
closing.cpp:115:12: error: 'ans' was not declared in this scope; did you mean 'abs'?
115 | return ans;
| ^~~
| abs
