#include "bits/stdc++.h"
#include "closing.h"
#define pb push_back
using namespace std;
const long long inf = 1e18 + 5;
const int MAXN = 2e5 + 5;
vector<int> curpath, path;
vector<long long> disx(MAXN), disy(MAXN);
vector<pair<int, int> > adj[MAXN];
void dfs(int node, int par, int target){
if(node == target){
path = curpath;
}
for(auto itr: adj[node]){
if(itr.first != par){
curpath.pb(itr.first);
dfs(itr.first, node, target);
curpath.pop_back();
}
}
}
void disc(int node, int par, long long dis, int type){
if(!type) disx[node] = dis;
else disy[node] = dis;
for(auto itr: adj[node]){
if(itr.first != par){
disc(itr.first, node, dis + itr.second, type);
}
}
}
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
for(int i = 0; i < N; i++){
adj[i].clear();
}
for(int i = 0; i < N-1; i++){
adj[U[i]].pb({V[i], W[i]});
adj[V[i]].pb({U[i], W[i]});
}
disc(X, X, 0, 0);
disc(Y, Y, 0, 1);
curpath.clear();
path.clear();
dfs(X, X, Y);
reverse(path.begin(), path.end());
path.pb(X);
reverse(path.begin(), path.end()); // X ..... Y
long long pathlen = disx[Y];
/*
vector<long long> take(N*2+10, inf);
take[0] = 0;
priority_queue<pair<long long, long long> > pq;
vector<int> vis(N);
for(auto itr: path){
vis[itr] = 1;
}
for(auto itr: adj[X]){
pq.push({-disx[itr.first], itr.first});
}
for(auto itr: adj[Y]){
pq.push({-disy[itr.first], itr.first});
}
int cnt = 0;
long long totdis = 0;
int make = 0;
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
long long val = min(disx[node], disy[node]);
if(val >= pathlen){
while(make > 0){
cnt++;
totdis += pathlen;
take[cnt] = totdis;
make--;
}
cnt++;
make++;
totdis += val;
take[cnt] = totdis;
}
else{
cnt++;
make++;
totdis += val;
take[cnt] = totdis;
}
for(auto itr: adj[node]){
if(!vis[itr.first]){
pq.push({-min(disx[itr.first], disy[itr.first]), itr.first});
}
}
}
while(make > 0){
cnt++;
totdis += pathlen;
take[cnt] = totdis;
make--;
}
for(int i = 0; i < N; i++){
vis[i] = 0;
}*/
vector<int> vis(N);
for(auto itr: path){
vis[itr] = 1;
}
int M = path.size();
vector<vector<vector<long long> > > dp(M+1, vector<vector<long long> > (4, vector<long long>(2*N+1, inf))); // 0 = bos, 1 = x, 2 = y, 3 = xy
dp[0][1][0] = 0;
for(int i = 0; i < M; i++){
dp[i+1][0] = dp[i][0]; // 0 -> 0
for(int j = 0; j <= N*2; j++){ // 1 -> 0
dp[i+1][0][j] = min(dp[i+1][0][j], dp[i][1][j]);
}
for(int j = 1; j <= N*2; j++){ // 1 -> 1
dp[i+1][1][j] = min(dp[i+1][1][j], dp[i][1][j-1] + disx[path[i]]);
}
for(int j = 1; j <= N*2; j++){ // 2 -> 2
dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][2][j-1] + disy[path[i]]);
}
for(int j = 1; j <= N*2; j++){ // 1 -> 2
dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][1][j-1] + disy[path[i]]);
}
for(int j = 1; j <= N*2; j++){ // 3 -> 2
dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][3][j-1] + disy[path[i]]);
}
for(int j = 1; j <= N*2; j++){ // 0 -> 2
dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][0][j-1] + disy[path[i]]);
}
for(int j = 2; j <= N*2; j++){ // 3 -> 3
dp[i+1][3][j] = min(dp[i+1][3][j], dp[i][3][j-2] + max(disx[path[i]], disy[path[i]]));
}
for(int j = 2; j <= N*2; j++){ // 1 -> 3
dp[i+1][3][j] = min(dp[i+1][3][j], dp[i][1][j-2] + max(disx[path[i]], disy[path[i]]));
}
// düz transitionlarım bitti şimdi 0 hariç caseine göre dp yapıp transition atcaz
for(int j = 0; j < N; j++){
vis[j] = 0;
}
for(auto itr: path){
vis[itr] = 1;
}
vector<long long> dpin(N*2+1, inf); // 1in dpsi
dpin[0] = 0;
priority_queue<pair<long long, long long> > pq;
for(auto itr: adj[path[i]]){
pq.push({-disx[itr.first], itr.first});
}
long long df = abs(disx[path[i]] - disy[path[i]]);
int cnt = 0, make = 0;
long long totdis = 0;
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
long long val = disx[node];
cnt++;
totdis += val;
dpin[cnt] = totdis;
for(auto itr: adj[node]){
if(!vis[itr.first]){
pq.push({-disx[itr.first], itr.first});
}
}
}
for(int l = N*2; l >= 0; l--){
for(int j = 0; j <= l; j++){
if(dpin[j] == inf) break;
dp[i+1][1][l] = min(dp[i+1][1][l], dp[i+1][1][l-j] + dpin[j]);
}
}
for(int j = 0; j < N; j++){
vis[j] = 0;
}
for(auto itr: path){
vis[itr] = 1;
}
//vector<long long> dpin(N*2+1, inf); // 1in dpsi
dpin.assign(N*2+1, inf);
dpin[0] = 0;
//priority_queue<pair<long long, long long> > pq;
for(auto itr: adj[path[i]]){
pq.push({-disy[itr.first], itr.first});
}
cnt = 0, make = 0;
totdis = 0;
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
long long val = disy[node];
cnt++;
totdis += val;
dpin[cnt] = totdis;
for(auto itr: adj[node]){
if(!vis[itr.first]){
pq.push({-disy[itr.first], itr.first});
}
}
}
for(int l = N*2; l >= 0; l--){
for(int j = 0; j <= l; j++){
if(dpin[j] == inf) break;
dp[i+1][2][l] = min(dp[i+1][2][l], dp[i+1][2][l-j] + dpin[j]);
}
}
for(int j = 0; j < N; j++){
vis[j] = 0;
}
for(auto itr: path){
vis[itr] = 1;
}
//vector<long long> dpin(N*2+1, inf); // 1in dpsi
dpin.assign(N*2+1, inf);
dpin[0] = 0;
//priority_queue<pair<long long, long long> > pq;
for(auto itr: adj[path[i]]){
pq.push({-min(disy[itr.first], disx[itr.first]), itr.first});
}
cnt = 0, make = 0;
totdis = 0;
while(!pq.empty()){
int node = pq.top().second;
pq.pop();
if(vis[node]) continue;
vis[node] = 1;
long long val = min(disx[node], disy[node]);
if(val >= df){
while(make > 0){
cnt++;
totdis += df;
dpin[cnt] = totdis;
make--;
}
cnt++;
make++;
totdis += val;
dpin[cnt] = totdis;
}
else{
cnt++;
make++;
totdis += val;
dpin[cnt] = totdis;
}
for(auto itr: adj[node]){
if(!vis[itr.first]){
pq.push({-min(disx[itr.first], disy[itr.first]), itr.first});
}
}
}
while(make > 0){
cnt++;
totdis += df;
dpin[cnt] = totdis;
make--;
}
for(int l = N*2; l >= 0; l--){
for(int j = 0; j <= l; j++){
if(dpin[j] == inf) break;
dp[i+1][3][l] = min(dp[i+1][3][l], dp[i+1][3][l-j] + dpin[j]);
}
}
/*
cout<<"index : "<<i+1<<endl;
for(int j = 0; j < 4; j++){
for(int take = 0; take <= N*2; take++){
cout<<j<<" "<<take<<" -> "<<dp[i+1][j][take]<<" "<<endl;
}
cout<<endl;
}*/
}
int ans = 0;
for(int i = 2; i < 4; i++){
for(int j = 0; j <= N*2; j++){
if(dp[M][i][j] <= K) ans = max(ans, j);
}
}
return ans;
}
