#include "closing.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
long long n,x,y,k;
vector<pair<long long,long long>> haha[200001];
vector<long long> bruh(200001);
vector<long long> wow(200001);
void dfs(long long a, long long t, long long d, bool yeah) {
if(yeah) {
bruh[a] = d;
}
else {
wow[a] = d;
}
for(pair<long long,long long> v: haha[a]) {
if(v.first != t) {
dfs(v.first,a,d+v.second,yeah);
}
}
}
bool dude(long long a, long long t) {
if(a == y) {
if(bruh[a] < wow[a]) {
k-=bruh[a];
wow[a]-=bruh[a];
bruh[a] = 0;
}
else {
k-=wow[a];
bruh[a]-=wow[a];
wow[a] = 0;
}
return true;
}
for(pair<long long,long long> v: haha[a]) {
if(v.first != t) {
if(dude(v.first,a)) {
if(bruh[a] < wow[a]) {
k-=bruh[a];
wow[a]-=bruh[a];
bruh[a] = 0;
}
else {
k-=wow[a];
bruh[a]-=wow[a];
wow[a] = 0;
}
return true;
}
}
}
return false;
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
n = N;
x = X;
y = Y;
k = K;
for(int i = 0; i < n; i++) {
haha[i].clear();
}
for(long long i = 0; i < n-1; i++) {
haha[U[i]].push_back({V[i],W[i]});
haha[V[i]].push_back({U[i],W[i]});
}
long long ans = 0;
dfs(x,-1,0,true);
dfs(y,-1,0,false);
vector<long long> wut(n);
for(long long i = 0; i < n; i++) {
wut[i] = min(bruh[i],wow[i]);
}
sort(wut.begin(),wut.end());
long long sb = 0;
for(long long i = 0; i < wut.size(); i++) {
sb+=wut[i];
if(sb > k) {
break;
}
ans++;
}
dude(x,-1);
if(k < 0) {
return ans;
}
vector<long long> dp(2*n+1,LLONG_MAX/3);
dp[0] = 0;
for(long long i = 0; i < n; i++) {
long long a = bruh[i],b = wow[i];
if(a > b) {
swap(a,b);
}
for(int j = 2*n; j >= 0; j--) {
if(j > 0) {
dp[j] = min(dp[j],dp[j-1]+a);
}
if(j > 1) {
dp[j] = min(dp[j],dp[j-2]+b);
}
}
}
for(long long i = 0; i <= 2*n; i++) {
if(dp[i] <= k) {
ans = max(ans,i);
}
}
return ans;
}
