#include "closing.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<pll> graph[200001];
ll dist[200001][2];
ll cost1[200001];
ll cost2[200001];
int level[200001];
int T[200001];
void dfs(int v, int pop, ll d, int w)
{
dist[v][w] = d;
forall(it,graph[v])
{
if(it.ff != pop) dfs(it.ff,v,d+it.ss,w);
}
}
int max_score(int n, int X, int Y, ll K, vi U, vi V, vi W)
{
rep(i,n) graph[i] = {};
rep(i,n-1)
{
graph[U[i]].pb({V[i],W[i]});
graph[V[i]].pb({U[i],W[i]});
}
dfs(X,X,0,0);
dfs(Y,Y,0,1);
rep(i,n)
{
cost1[i] = min(dist[i][0],dist[i][1]);
cost2[i] = max(dist[i][0],dist[i][1]) - cost1[i];
}
rep(i,n)
{
if(dist[i][0] + dist[i][1] == dist[Y][0]) T[i] = 0;
else if(cost1[i] <= cost2[i]) T[i] = 1;
else T[i] = 2;
}
int ans1 = 0;
vl d;
rep(i,n) d.pb(cost1[i]);
ll used = 0;
sort(all(d));
forall(it,d)
{
used += it;
if(used > K) break;
ans1++;
}
int ans2 = 0;
used = 0;
rep(i,n)
{
if(T[i] == 0)
{
ans2++;
used += cost1[i];
level[i] = 1;
}
}
if(used > K) return ans1;
priority_queue<pll,vector<pll>,greater<pll>> pq;
priority_queue<pll,vector<pll>,greater<pll>> pq2;
rep(i,n)
{
if(T[i] < 2)
{
if(level[i] == 0) pq.push({cost1[i],i});
pq.push({cost2[i],i});
}
else
{
pq2.push({cost1[i]+cost2[i],i});
}
}
while(!pq.empty() && !pq2.empty())
{
if(siz(pq) == 0)
{
if(used + pq2.top().ff <= K)
{
pll t = pq2.top();
pq2.pop();
ans2+=2;
used+=t.ff;
level[t.ss] = 2;
continue;
}
else break;
}
if(siz(pq2) == 0)
{
if(used + pq.top().ff <= K)
{
pll t = pq.top();
pq.pop();
ans2++;
used+=t.ff;
level[t.ss]++;
}
else break;
}
ll c1 = pq.top().ff;
pll xd = pq.top();
pq.pop();
if(siz(pq) != 0) c1 += pq.top().ff;
else c1 += 1e18;
pq.push(xd);
ll c2 = pq2.top().ff;
if(used + min(c1,c2) > K)
{
if(used+pq.top().ff <= K)
{
ans2++;
used += pq.top().ff;
level[pq.top().ss]++;
pq.pop();
continue;
}
break;
}
if(c1 < c2)
{
ans2 += 2;
used += c1;
pll t = pq.top();
pq.pop();
level[t.ss]++;
t = pq.top();
pq.pop();
level[t.ss]++;
}
else
{
ans2 += 2;
used += c2;
pll t = pq2.top();
pq2.pop();
level[t.ss] = 2;
}
}
vl p;
rep(i,n)
{
if(T[i] == 2 && level[i] == 0) p.pb(cost1[i]);
}
sort(all(p));
forall(it,p)
{
used += it;
if(used > K) break;
ans2++;
}
return max(ans1,ans2);
}
