#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;
}
int ans = 0;
vector<long long> pre(path.size());
for(int i = 1; i < path.size(); i++){
pre[i] = pre[i-1] + disx[path[i]];
}
vector<long long> suf(path.size());
for(int i = path.size()-2; i >= 0; i--){
suf[i] = suf[i+1] + disy[path[i]];
}
vector<long long> cik(path.size()+1);
for(int i = 0; i < path.size(); i++){
cik[i+1] = cik[i] - min(disx[path[i]], disy[path[i]]);
}
for(int xr = 0; xr < path.size(); xr++){
for(int yl = 0; yl < path.size(); yl++){
long long discalc;
if(xr < yl){
discalc = pre[xr] + suf[yl];
}
else{
discalc = pre[xr] + suf[yl] + (cik[xr+1] - cik[yl]);
}
int anscalc = (xr + 1) + (path.size() - yl);
if(discalc > K) continue;
int l = 0, r = N*2;
while(l < r){
int m = (l + r + 1)/2;
if(take[m] + discalc <= K) l = m;
else r = m-1;
}
ans = max(ans, anscalc + l);
/*
for(int i = 0; i <= N*2; i++){
long long dishere = discalc + take[i];
if(dishere > K) break;
int anshere = anscalc + i;
ans = max(ans, anshere);
//cout<<xr<<" "<<yl<<" "<<i<<" üclüsü icin best = "<<anshere<<endl;
}
*/
}
}
return ans;
}
