#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma gcc-optimize("O3, unrolls-loops")
const int nx=2e5+5;
vector<pair<ll, ll>> g[nx];
struct segtree
{
struct node
{
ll sm, f;
node(ll sm=0, ll f=0): sm(sm), f(f){}
friend node operator+(const node &a, const node &b) {return node(a.sm+b.sm, a.f+b.f);}
} d[4*nx];
void build(int l, int r, int i)
{
d[i]=node(0, 0);
if (l==r) return;
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
}
void update(int l, int r, int i, int idx, int f, ll vl)
{
if (idx<l||r<idx) return;
if (l==r) return d[i]=node(d[i].sm+f*vl, d[i].f+f), void();
int md=(l+r)/2;
update(l, md, 2*i, idx, f, vl);
update(md+1, r, 2*i+1, idx, f, vl);
d[i]=d[2*i]+d[2*i+1];
}
ll query(int l, int r, int i, ll vl)
{
if (vl>=d[i].sm) return d[i].f;
if (l==r) return 0;
int md=(l+r)/2;
if (d[2*i].sm>vl) return query(l, md, 2*i, vl);
else return d[2*i].f+query(md+1, r, 2*i+1, vl-d[2*i].sm);
}
} s;
void dfs(int u, int p, ll cw, vector<ll> &x)
{
x[u]=cw;
for (auto [v, w]:g[u]) if (v!=p) dfs(v, u, cw+w, x);
}
int max_score2(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();
for (int i=0; i<U.size(); i++) g[U[i]].push_back({V[i], W[i]}), g[V[i]].push_back({U[i], W[i]});
int res=0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
vector<ll> vs(N);
vs[X]=vs[Y]=1;
pq.push({0, X});
pq.push({0, Y});
while (!pq.empty())
{
auto [a, u]=pq.top();
pq.pop();
if (a>K) break;
K-=a;
res++;
vs[u]=1;
for (auto [v, w]:g[u]) if (!vs[v]) pq.push({a+w, v});
}
return res;
}
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-1; i++) if (U[i]!=i||V[i]!=i+1) return max_score2(N, X, Y, K, U, V, W);
if (X>Y) swap(X, Y);
for (int i=0; i<N; i++) g[i].clear();
for (int i=0; i<N-1; i++) g[U[i]].push_back({V[i], W[i]}), g[V[i]].push_back({U[i], W[i]});
vector<ll> a(N), b(N), idxa(N), idxb(N);
ll mx=0, t=0;
map<pair<ll, ll>, ll> mp;
dfs(X, X, 0, a);
dfs(Y, Y, 0, b);
for (int i=0; i<N; i++) mp[{a[i], 1}]=0, mp[{b[i], 2}]=0;
for (auto &[x, y]:mp) y=++t;
for (int i=0; i<N; i++) idxa[i]=mp[{a[i], 1}], idxb[i]=mp[{b[i], 2}];
priority_queue<ll, vector<ll>, greater<ll>> pq;
for (int i=0; i<N; i++) pq.push(a[i]), pq.push(b[i]);
ll tmp=K;
while (!pq.empty()&&pq.top()<=tmp) mx++, tmp-=pq.top(), pq.pop();
for (int i=0; i<N; i++)
{
s.build(1, 2*N, 1);
ll cur=0, res=0;
for (int j=0; j<=min(i-1, X); j++) s.update(1, 2*N, 1, idxa[j], 1, a[j]);
for (int j=X+1; j<i; j++) cur+=a[j], res++;
for (int j=i; j<Y; j++) cur+=b[j], res++;
for (int j=max(i, Y); j<N; j++) s.update(1, 2*N, 1, idxb[j], 1, b[j]);
for (int j=i; j<N; j++)
{
cur+=max(a[j], b[j]);
res+=2;
if (j<Y) res--, cur-=b[j];
else s.update(1, 2*N, 1, idxb[j], -1, b[j]);
if (cur>K) break;
mx=max(mx, res+s.query(1, 2*N, 1, K-cur));
}
}
return mx;
}
