#include "closing.h" #include <bits/stdc++.h> using namespace std; using lint = long long; using pi = array<lint, 2>; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() const int MAXN = 200005; pair<vector<lint>, vector<lint>> doConvex(vector<pi> p) { vector<lint> v; for (auto &[a, b] : p) { v.push_back(a); v.push_back(b - a); } sort(all(v)); reverse(all(v)); v.insert(v.begin(), 0); for (int i = 1; i < sz(v); i++) v[i] += v[i - 1]; vector<lint> ans[2]; for (int i = 0; i < sz(v); i++) { ans[(i + 1) % 2].push_back(v[i]); } return make_pair(ans[0], ans[1]); } pair<vector<lint>, vector<lint>> doConcave(vector<pi> p) { vector<lint> v[2]; sort(all(p), [&](const pi &a, const pi &b) { return a[1] > b[1]; }); vector<lint> curmin(sz(p) + 1); curmin[sz(p)] = -2e18; for (int i = sz(p) - 1; i >= 0; i--) { curmin[i] = max(curmin[i + 1], p[i][0]); } lint sum = 0; v[1].push_back(0); for (int i = 0; i < sz(p); i++) { sum += p[i][1]; v[1].push_back(sum); } sum = 0; lint bamax = -2e18; for (int i = 0; i < sz(p); i++) { sum += p[i][1]; bamax = max(bamax, p[i][0] - p[i][1]); v[0].push_back(max(sum + bamax, sum - p[i][1] + curmin[i])); } for (int i = 1; i + 1 < sz(v[0]); i++) { lint le = v[0][i] - v[0][i - 1]; lint ri = v[0][i + 1] - v[0][i]; assert(le >= ri); } return make_pair(v[0], v[1]); } vector<lint> solve(vector<pi> inp) { int n = sz(inp); lint sum = 0; vector<pi> convex, concave; for (auto &[a, b] : inp) { sum += b; a = b - a; if (a * 2 >= b) convex.push_back({a, b}); else concave.push_back({a, b}); } auto [odd1, even1] = doConcave(concave); auto [odd2, even2] = doConvex(convex); auto conv = [&](vector<lint> a, vector<lint> b) { if (sz(a) == 0) return b; if (sz(b) == 0) return a; vector<lint> v; lint sum = a[0] + b[0]; for (int i = 1; i < sz(a); i++) v.push_back(a[i] - a[i - 1]); for (int i = 1; i < sz(b); i++) v.push_back(b[i] - b[i - 1]); sort(all(v)); reverse(all(v)); v.insert(v.begin(), sum); for (int i = 1; i < sz(v); i++) v[i] += v[i - 1]; return v; }; vector<lint> ans(2 * n + 1, 0); { auto comb1 = conv(odd1, odd2); for (int i = 0; i < sz(comb1) && 2 * i + 2 < sz(ans); i++) ans[2 * i + 2] = max(ans[2 * i + 2], comb1[i]); } { auto comb1 = conv(odd1, even2); for (int i = 0; i < sz(comb1) && 2 * i + 1 < sz(ans); i++) ans[2 * i + 1] = max(ans[2 * i + 1], comb1[i]); } { auto comb1 = conv(even1, odd2); for (int i = 0; i < sz(comb1) && 2 * i + 1 < sz(ans); i++) ans[2 * i + 1] = max(ans[2 * i + 1], comb1[i]); } { auto comb1 = conv(even1, even2); for (int i = 0; i < sz(comb1) && 2 * i + 0 < sz(ans); i++) ans[2 * i + 0] = max(ans[2 * i + 0], comb1[i]); } for (auto &x : ans) x = sum - x; reverse(all(ans)); return ans; } vector<vector<pi>> gph; int par[MAXN]; lint dist[2][MAXN]; void dfs(int x, int p, int d) { for (auto &[w, y] : gph[x]) { if (y == p) continue; dist[d][y] = dist[d][x] + w; par[y] = x; dfs(y, x, d); } } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { gph.clear(); gph.resize(N); for (int i = 0; i < N - 1; i++) { gph[U[i]].push_back({W[i], V[i]}); gph[V[i]].push_back({W[i], U[i]}); } for (int i = 0; i < N; i++) dist[0][i] = dist[1][i] = 0; dfs(Y, -1, 1); dfs(X, -1, 0); vector<int> chk(N); vector<int> paths; for (int i = Y; i != X; i = par[i]) { paths.push_back(i); chk[i] = 1; } paths.push_back(X); reverse(all(paths)); chk[X] = 1; vector<pi> coins; for (int i = 0; i < N; i++) { if (!chk[i]) { coins.push_back({dist[0][i], dist[1][i]}); } } for (auto &[x, y] : coins) if (x > y) swap(x, y); auto s1 = solve(coins); vector<lint> s2(sz(paths), 2e18); { vector<lint> g1(sz(paths)), g2(sz(paths)); lint tot = 0; for (int i = 0; i < sz(paths); i++) { tot += max(dist[1][paths[i]], dist[0][paths[i]]); g1[i] = max(dist[1][paths[i]], dist[0][paths[i]]) - dist[0][paths[i]]; g2[i] = max(dist[1][paths[i]], dist[0][paths[i]]) - dist[1][paths[i]]; } int l = 0, r = sz(paths); while (l < r) { s2[r - l - 1] = min(s2[r - l - 1], tot); if (g1[l] > g2[r - 1]) { tot -= g1[l++]; } else tot -= g2[--r]; } } int ans = 0; int j = sz(s2); for (int i = 0; i < sz(s1); i++) { while (j && s1[i] + s2[j - 1] > K) j--; if (j) ans = max(ans, i + j + sz(paths)); } { lint cursum = 0; vector<lint> sums; for (int i = 0; i < N; i++) { sums.push_back(dist[0][i]); sums.push_back(dist[1][i]); } sort(all(sums)); for (int i = 0; i < sz(sums); i++) { cursum += sums[i]; if (cursum > K) break; ans = max(ans, i + 1); } } return ans; }