#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<class T> bool chmax(T& a, const T& b) {return a < b ? a = b, 1 : 0;}
#define rep(i,a,b) for (int i = a; i < b; i++)
#define rev(i,a,b) for (int i = a; i >= b; i--)
#define sz(x) ((int) (x).size())
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#ifdef LOCAL
#define dbg(x) cout << #x << " = " << x << "\n"
#else
#define dbg(x)
#endif
/*
weighted edges denoting the time, given a fixed budget k, determine the max
Σ(1 if city[i] can be reached from node x) + Σ(1 if city[i] can be reached from node y)
where a node is reachable iff ct[i] >= Σ(edges on shortest path to i)
the graph is a tree
*/
struct Fenw {
int n; vector<ll> BIT;
Fenw(int N = 0) : n(N), BIT(N, 0) {}
void update(int r, ll delta) {for (; r < n; r |= r+1) BIT[r] += delta;}
void update(int l, int r, ll delta) {update(l, delta); update(r+1, -delta);}
ll query(int i) {ll res = 0; for (; i >= 0; i &= i+1, i--) res += BIT[i]; return res;}
};
const int MAXN = 200'000, MAXLOG = 19;
int n, m, timer = 0;
vector<vector<pi>> G;
void dfs(int u, int p, ll d, vl &dist_root, vi &tin, vi &tout, vvi &up) {
tin[u] = timer++;
up[u][0] = p;
for (int i = 1; i < MAXLOG; i++) {
up[u][i] = up[up[u][i-1]][i-1];
}
dist_root[u] = d;
for (auto [v, w] : G[u]) {
if (v == p) continue;
dfs(v, u, d+w, dist_root, tin, tout, up);
}
tout[u] = timer++;
}
// bool is_ancestor(int u, int v, vi &tin, vi &tout) {
// return tin[u] <= tin[v] && tout[u] >= tout[v];
// }
// int lca(int u, int v) {
// if (is_ancestor(u, v)) return u;
// if (is_ancestor(v, u)) return v;
// rev(i, MAXLOG-1, 0) {
// if (!is_ancestor(up[u][i], v)) u = up[u][i];
// }
// return up[u][0];
// }
// ll dist(int u, int v) {
// int c = lca(u, v);
// return dist_root[u] + dist_root[v] - 2 * dist_root[c];
// }
int max_score(int N, int x, int y, ll k, vi U,vi V,vi W) {
n = N, m = sz(U);
G.assign(n, vector<pi>()); rep(i, 0, m) G[U[i]].push_back({V[i], W[i]}), G[V[i]].push_back({U[i], W[i]});
timer = 0;
vvi upx(n, vi(MAXLOG));
vi tinx(n), toutx(n); vl dist_rootx(n);
dfs(x,x,0,dist_rootx,tinx,toutx,upx);
timer = 0;
vvi upy(n, vi(MAXLOG));
vi tiny(n), touty(n); vl dist_rooty(n);
dfs(y,y,0, dist_rooty, tiny, touty, upy);
auto xw = Fenw(2*n+2), yw = Fenw(2*n+2);
rep(i, 0, n) {
xw.update(tinx[i], toutx[i], dist_rootx[i]);
yw.update(tiny[i], touty[i], dist_rooty[i]);
}
vi state(n);
rep(i, 0, 2*n) {
int best = -1; ll bestw = 4e18;
rep(u, 0, n) {
if (state[u] == 2) continue;
if (state[u] == 0) {
ll d = min(xw.query(tinx[u]), yw.query(tiny[u]));
if (d < bestw || best == -1) best = u, bestw = d;
} else {
ll d = max(xw.query(tinx[u]), yw.query(tiny[u])) - min(xw.query(tinx[u]), yw.query(tiny[u]));
if (d < bestw || best == -1) best = u, bestw = d;
}
}
if (bestw > k) break;
if (best == -1) break;
k -= bestw;
state[best]++;
xw.update(tinx[best], toutx[best], -bestw);
yw.update(tiny[best], touty[best], -bestw);
}
// priority_queue<pi, vector<pi>, greater<pi>> pq;
// rep(i, 0, n) pq.push({min(dist(x,i), dist(y,i)), i});
// while (!pq.empty()) {
// auto [w,u] = pq.top(); pq.pop();
// if (w>k) break;
// if (state[u] == 0) {
// state[u] = 1;
// pq.push({max(dist(x,u),dist(y,u))-min(dist(x,u),dist(y,u)), u});
// k -= w;
// } else {
// state[u] = 2;
// k -= w;
// }
// }
int ans = accumulate(all(state), 0);
return ans;
}
