#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<ll, 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
*/
const int MAXN = 200'000, MAXLOG = 19;
int n, m, timer = 0;
int tin[MAXN+5] = {}, tout[MAXN+5] = {}; ll dist_root[MAXN+5] = {};
vector<vector<pi>> G;
vvi up;
void dfs(int u, int p, ll d) {
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);
}
tout[u] = timer++;
}
bool is_ancestor(int u, int v) {
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]});
up.assign(n, vi(MAXLOG));
vi state(n);
dfs(0,0,0);
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)), u});
k -= w;
} else {
state[u] = 2;
k -= w;
}
}
int ans = accumulate(all(state), 0);
return ans;
}
