#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const int c=200005;
vector<pair<int, long long> > sz[c];
vector<pair<int, long long> > sor;
long long n, dist[c][2], bal, jobb, len, pref[2*c], inf=1e18;
bool ut[c];
void dfs(int a, int el, long long tav, int id) {
dist[a][id]=tav;
for (auto p:sz[a]) {
int x=p.first;
long long y=tav+p.second;
if (x!=el) {
dfs(x, a, y, id);
}
}
}
bool dfs2(int a, int el, long long tav) {
if (a==jobb) {
sor.push_back({a, tav});
ut[a]=1;
return true;
}
for (auto p:sz[a]) {
int x=p.first;
long long y=tav+p.second;
if (x!=el) {
if (dfs2(x, a, y)) {
sor.push_back({a, tav});
ut[a]=1;
return true;
}
}
}
return false;
}
long long calc(long long ert) {
if (ert<0) {
return -inf;
}
int lo=0, hi=2*n+1, mid;
while (hi-lo>1) {
mid=(hi+lo)/2;
if (pref[mid]<=ert) {
lo=mid;
} else {
hi=mid;
}
}
return lo;
}
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;
for (int i=0; i<n-1; i++) {
int a=U[i], b=V[i], c=W[i];
sz[a].push_back({b, c});
sz[b].push_back({a, c});
}
bal=X, jobb=Y;
dfs(bal, -1, 0, 0), dfs(jobb, -1, 0, 1);
len=dist[jobb][0];
long long spec=0, maxi=0;
if (true) {
vector<long long> p;
for (int i=0; i<n; i++) {
p.push_back(dist[i][0]);
p.push_back(dist[i][1]);
}
sort(p.begin(), p.end());
long long sum=0, cnt=0;
for (auto x:p) {
if (sum+x<=K) {
sum+=x;
cnt++;
}
}
spec=cnt;
}
bool s=dfs2(bal, -1, 0);
reverse(sor.begin(), sor.end());
long long si=sor.size(), sum=0, cnt=0, kezd=0, veg=si-1;
while (kezd<=veg) {
if (sor[kezd].second<=len-sor[veg].second) {
cnt++;
sum+=sor[kezd].second;
kezd++;
} else {
cnt++;
sum+=len-sor[veg].second;
veg--;
}
}
vector<long long> add;
for (int i=kezd; i<si; i++) {
add.push_back(2*sor[i].second-len);
}
for (int i=0; i<=veg; i++) {
add.push_back(len-2*sor[i].second);
}
for (int i=1; i<=2*n; i++) {
pref[i]=inf;
}
vector<pair<long long, long long> > dupla;
vector<long long> prefmax, sufmin;
for (int i=0; i<n; i++) {
if (ut[i]) {
continue;
}
long long a=dist[i][0], b=dist[i][1];
if (a>b) {
swap(a, b);
}
if (2*a<=b) {
add.push_back(a);
add.push_back(b-a);
} else {
dupla.push_back({b, a});
}
}
sort(add.begin(), add.end());
assert(add[0]>=0);
for (int i=0; i<add.size(); i++) {
pref[i+1]=pref[i]+add[i];
}
if (dupla.size()>0) {
sort(dupla.begin(), dupla.end());
int ds=dupla.size();
prefmax.resize(ds), sufmin.resize(ds);
prefmax[0]=dupla[0].first-dupla[0].second;
for (int i=1; i<ds; i++) {
prefmax[i]=max(prefmax[i-1], dupla[i].first-dupla[i].second);
}
sufmin[ds-1]=dupla[ds-1].second;
for (int i=ds-2; i>=0; i--) {
sufmin[i]=min(sufmin[i+1], dupla[i].second);
}
maxi=max(maxi, cnt+calc(K-sum));
maxi=max(maxi, cnt+1+calc(K-sum-sufmin[0]));
for (int i=0; i<ds; i++) {
sum+=dupla[i].first;
maxi=max(maxi, cnt+2*i+1+calc(K-sum+prefmax[i]));
maxi=max(maxi, cnt+2*i+2+calc(K-sum));
if (i+1<ds) {
maxi=max(maxi, cnt+2*i+3+calc(K-sum-sufmin[i+1]));
}
}
}
maxi=max(maxi, cnt+calc(K-sum));
for (int i=0; i<=n; i++) {
sz[i].clear();
ut[i]=0;
}
sor.clear();
len=0;
return max(maxi, spec);
}
