#include "bits/stdc++.h"
#include "closing.h"
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define sz(x) ((int)(x).size())
#define pb push_back
#define s second
#define f first
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
const int N=3e3+10;
ll k, d[N][2], dp[2*N][N], mn[N], mx[N];
vector<pii> ad[N];
int n, x, y;
void build(int u, int in, int pst=-1) {
for(auto [nxt, w] : ad[u]) {
if(nxt==pst) continue;
d[nxt][in]=d[u][in]+w;
build(nxt, in, u);
}
}
vi path, now;
void get_path(int u, int pst=-1) {
now.pb(u);
if(u==y) {
path=now;
return;
}
for(auto [it, w] : ad[u]) {
if(it==pst) continue;
get_path(it, u);
}
now.pop_back();
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
path.clear(); now.clear();
n=N; x=X; y=Y; k=K;
FOR(i, 0, n) ad[i].clear();
FOR(i, 0, n-1) {
ad[U[i]].pb({V[i],W[i]});
ad[V[i]].pb({U[i],W[i]});
}
d[x][0]=d[y][1]=0;
build(x, 0);
build(y, 1);
get_path(x);
FOR(i, 0, n) mn[i+1]=min(d[i][0], d[i][1]), mx[i+1]=max(d[i][0], d[i][1]);
vector<ll> inf;
FOR(i, 1, n+1) inf.pb(mn[i]);
sort(inf.begin(), inf.end());
ll now_sum=0; int ans=0;
for(auto it : inf) {
if(now_sum+it>k) break;
now_sum+=it;
ans++;
}
now_sum=0;
vector dif(n+1, false);
for(auto it : path) {
dif[it+1]=true;
now_sum+=mn[it+1];
}
FOR(i, 0, 2*n+1) FOR(j, 0, n+1) dp[i][j]=1e18;
FOR(j, 0, n+1) dp[sz(path)][j]=now_sum;
FOR(i, 1, 2*n+1) {
FOR(j, 1, n+1) {
if(dif[j]) {
if(i>=1) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+mx[j]-mn[j]);
}
else {
if(i>=1) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+mn[j]);
if(i>=2) dp[i][j]=min(dp[i][j], dp[i-2][j-1]+mx[j]);
}
dp[i][j]=min(dp[i][j], dp[i][j-1]);
}
}
for(int i=2*n; i>=0; i--) {
if(dp[i][n]<=k) ans=max(ans, i);
}
return ans;
}
/*
1
5 0 3 11
0 1 5
1 2 1
2 3 6
3 4 5
1
7 0 2 10
0 1 2
0 3 3
1 2 4
2 4 2
2 5 5
5 6 3
1
4 0 3 20
0 1 18
1 2 1
2 3 19
1
8 1 3 14
0 1 3
1 2 2
2 3 1
3 4 5
4 5 2
5 6 3
6 7 1
*/
