#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define cerr if(0) cerr
#define cout if(0) cout
const int N = 4e5+100, M = 3e5;
const ll INF = 1e18;
multiset<ll> S[N];
ll A[M], B[M], C[M], dp[N]; // 0 - 1
vector<pair<int, ll>> g[M];
vector<ll> DP[N];
bitset<M> in_path;
int sz[M];
bool dfs(int v, int p, int t, vector<int> &T){
T.pb(v);
if(v == t){
return 1;
}
for(auto [u, w]: g[v]){
if(u != p){
bool ok = dfs(u, v, t, T);
if(ok) return true;
}
}
T.pop_back();
return false;
}
void dfs2(int v, int p){
vi U;
sz[v] = 1;
int big = -1;
for(auto [u, w]: g[v]){
if(u != p && !in_path[u]){
dfs2(u, v);
sz[v] += sz[u];
U.pb(u);
if(big == -1 || sz[big] < sz[u]) big = u;
}
}
if(big == -1){
S[v].insert(A[v]);
return;
}
S[v].swap(S[big]);
for(int u: U){
if(u != big){
for(ll x: S[u]) S[v].insert(x);
}
}
S[v].insert(A[v]);
}
int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i = 0; i < n; ++i) g[i].clear(), S[i].clear(), DP[i].clear();
in_path = 0;
for(int i = 0; i < n-1; ++i){
g[U[i]].pb({V[i], W[i]});
g[V[i]].pb({U[i], W[i]});
}
vector<ll> dist(n, -1);
dist[X] = 0;
queue<int> q;
q.push(X);
while(!q.empty()){
int v = q.front(); q.pop();
for(auto [u, w]: g[v]){
if(dist[u] == -1){
dist[u] = dist[v] + w;
q.push(u);
}
}
}
vector<ll> dist2(n, -1);
dist2[Y] = 0;
q.push(Y);
while(!q.empty()){
int v = q.front(); q.pop();
for(auto [u, w]: g[v]){
if(dist2[u] == -1){
dist2[u] = dist2[v] + w;
q.push(u);
}
}
}
for(int i = 0; i < n; ++i){
A[i] = min(dist[i], dist2[i]);
B[i] = max(dist[i], dist2[i]) - min(dist[i], dist2[i]);
}
vi T;
dfs(X, X, Y, T);
for(int x: T) in_path[x] = 1;
ll sum = 0;
for(int x: T){
sum += A[x];
}
int ans = 0;
ll KK = K;
for(int j = 0; j < n; ++j) C[j] = A[j];
sort(C, C+n);
for(int j = 0; j < n; ++j){
if(KK>= C[j]) KK-=C[j], ++ans;
}
if(dist[Y] > 2*K) return ans;
for(int x: T){
K -= A[x];
A[x] = 0;
}
priority_queue<array<ll, 3>> Q;
for(int v: T){
dfs2(v, v);
dp[0] = 0;
auto it = S[v].begin();
// cout << v << ' ' << B[v] << ' ' << ":\n";
// for(ll x: S[v]) cout << x << ' ';
// cout << '\n';
// cout << '\n';
int cnt = 0;
for(int i = 1; i <= sz[v]*2; ++i, ++it){
if(it == S[v].end()){
if((*prev(it)) < B[v]){
for(int j = i; j <= sz[v] * 2; ++j){
Q.push({-B[v]*2, -INF, -1});
}
}else{
// Q.push({-((*prev(it)) + B[v]), (*prev(it))});
assert(cnt == 1);
}
break;
}else{
if(B[v] > (*it)){
Q.push({-(*it) * 2, -INF, -1});
++cnt;
continue;
}
if(cnt == 1){
if(B[v] > (*prev(it))){
Q.push({-2*B[v], -INF, -1});
}
// Q.push({-((*prev(it)) + B[v]), (*prev(it))});
++i;
Q.push({-(*it)*2, -INF, v});
}else{
while(B[v] <= (*it) && cnt){
--cnt;
Q.push({-B[v]*2, -INF, -1});
++i;
}
Q.push({-(*it) * 2, -INF, v});
++cnt;
}
}
}
}
dp[0] = 0;
int cur = 1;
while(!Q.empty()){
ll x = -Q.top()[0];
ll y = -Q.top()[1];
int v = Q.top()[2];
Q.pop();
cout << x << ' ' << y << ' ' << v << '\n';
if(y == INF){
dp[cur] = dp[cur - 1] + x / 2;
if(v != -1){
cout << v << ' ' << B[v] << " push\n";
Q.push({-x/2-B[v], x/2, -1});
}
}else{
dp[cur] = dp[cur - 1] + x + y;
}
// dp[cur] = dp[cur - 1] + -Q.top()[0] - (Q.top()[1] == -INF ? 0ll : Q.top()[1]);
// cout << Q.top()[0] << ' ' << Q.top()[1] << " f\n";
++cur;
}
assert(cur == 2*n+1);
for(int i = 0; i <= 2*n; ++i) cout << dp[i] << ' ' << "\n";
for(int i = 2*n; i >= 0; --i) if(dp[i] <= K) return max(i, ans);
return ans;
}
