#include "closing.h"
#include <bits/stdc++.h>
#include <vector>
#define int long long
using namespace std;
int n;
int INF = 1LL<<61;
vector<int> dist1;
vector<int> dist2;
vector<vector<pair<int,int>>> adjlist;
void dfs1(int node, int par) {
for (pair<int,int> j:adjlist[node]) {
if (j.first!=par) {
dist1[j.first] = dist1[node]+j.second;
dfs1(j.first,node);
}
}
}
void dfs2(int node, int par) {
for (pair<int,int> j:adjlist[node]) {
if (j.first!=par) {
dist2[j.first] = dist2[node]+j.second;
dfs2(j.first,node);
}
}
}
signed max_score(signed N, signed X, signed Y, long long K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) {
n=N;
dist1=dist2=vector<int>(n,INF);
adjlist=vector<vector<pair<int,int>>>(n);
for (int i=0; i<n-1; i++) {
adjlist[U[i]].push_back({V[i],W[i]});
adjlist[V[i]].push_back({U[i],W[i]});
}
dist1[X] = 0; dist2[Y] = 0;
dfs1(X,-1); dfs2(Y,-1);
vector<int> dp(2*n+1,INF); //max cost to get this amount of score
dp[0] = 0;
vector<int> sc1cost(dist1.begin(), dist1.end());
vector<int> sc2cost(dist2.begin(), dist2.end());
for (int i=0; i<n; i++) {
if (dist1[i]>dist2[i]) {
swap(sc1cost[i],sc2cost[i]);
}
}
for (int i=0; i<n; i++) {
//cout << i <<" " << dist1[i] <<" " << dist2[i] << endl;
}
int mans = -1;
//first case: we do not fill up the path from X to Y
//in that case we don't want to place 2s anywhere
//so just take the cheapest 1s
int ct=0;
vector<int> indices(n); iota(indices.begin(), indices.end(), (int)0);
sort(indices.begin(), indices.end(), [&](const int i1, const int i2) {
return sc1cost[i1]<sc1cost[i2];
});
int parsum = 0;
for (int i=0; i<n; i++) {
if (parsum+sc1cost[indices[i]]>K) break;
parsum+=sc1cost[indices[i]];
ct++;
}
mans=max(mans,ct);
if (dist1[Y]>2*K) {
return mans;
}
//second case: need to take everything on the path from X to Y at least 1
//so we consider the 1s and 2s separately
int usedcost = 0;
vector<int> pathvals;
vector<pair<int,int>> remcosts;
int got = 0;
for (int i=0; i<n; i++) {
if (dist1[i]+dist2[i]==dist1[Y]) {
pathvals.push_back(i);
usedcost+=sc1cost[i];
got++;
remcosts.push_back({sc2cost[i]-sc1cost[i],INF});
}
else {
remcosts.push_back({sc1cost[i],sc2cost[i]});
}
}
K-=usedcost;
for (int i=0; i<remcosts.size(); i++) {
for (int prevscore=2*n; prevscore>=0; prevscore--) {
if (prevscore<=2*n-1) {
dp[prevscore+1] = min(dp[prevscore+1],dp[prevscore]+remcosts[i].first);
}
if (prevscore<=2*n-2) {
dp[prevscore+2] = min(dp[prevscore+2],dp[prevscore]+remcosts[i].second);
}
}
}
for (int i=0; i<=2*n; i++) {
//cout << i <<" " << dp[i] << endl;
if (dp[i]<=K) {
mans=max(mans,i+got);
}
}
return mans;
}
