#include "closing.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;

int par[MX];
ll A[MX],B[MX];
vector<pair<int,int>> adj[MX];
bool vis[MX], calc[MX];

void dfs(int v, int p) {
        par[v]=p;
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                A[u]=A[v]+w;
                dfs(u,v);
        }
}

void dfs2(int v, int p) {
        for(auto [u,w]:adj[v]) {
                if(u==p) continue;
                B[u]=B[v]+w;
                dfs2(u,v);
        }
}

// called multiple times
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W) {

        for(int i=0;i<N;i++) {
                adj[i].clear();
                vis[i]=calc[i]=false;
                par[i]=-1;
                A[i]=B[i]=0;
        }

        for(int i=0;i<N-1;i++) {
                adj[U[i]].push_back({V[i],W[i]});
                adj[V[i]].push_back({U[i],W[i]});
        }

        dfs(X,-1);
        dfs2(Y,-1);

        priority_queue<pair<ll,ll>> pq;

        int v=Y;
        vector<int> path;
        while(v!=X) {
                path.push_back(v);
                v=par[v];
        }
        path.push_back(X);
        v=Y;
        while(v!=X) {
                if(A[par[v]]<B[par[v]]) {
                        pq.push({-abs(A[par[v]]-B[par[v]]),par[v]});
                        pq.push({-abs(A[v]-B[v]),v});
                        vis[par[v]]=true;
                        vis[v]=true;
                        break;
                }       
                v=par[v];
        }

        int ans=0,cnt=0;
        ll sum=0;

        vector<ll> vals;
        for(int i=0;i<N;i++) vals.push_back(min(A[i],B[i]));
        sort(vals.begin(),vals.end());

        ll cur=0;
        for(int i=0;i<N;i++) {
                cur+=vals[i];
                if(cur<=K) ans=max(ans,i+1);
        }

        while(!pq.empty()) {
                auto [d,v]=pq.top(); pq.pop();
                d=-d;
                calc[v]=true;

                cnt+=2;
                sum+=min(A[v],B[v]);
                sum+=d;

                ll cur=sum;
                vector<int> del;
                for(auto x:path) {
                        if(!calc[x]) {
                                cur+=min(A[x],B[x]);
                                del.push_back(x);
                                calc[x]=true;
                                cnt++;
                        }
                }

                vector<pair<ll,ll>> vals;
                for(int i=0;i<N;i++) {
                        if(!calc[i]) {
                                vals.push_back({min(A[i],B[i]),i});
                        }
                }
                sort(vals.begin(),vals.end());

                for(int i=0;i<vals.size();i++) {
                        if(cur+vals[i].first>K) break;
                        cur+=vals[i].first;
                        cnt++;
                        del.push_back(vals[i].second);
                }

                if(cur<=K) ans=max(ans,cnt);

                for(auto [u,w]:adj[v]) {
                        if(!vis[u]) {
                                vis[u]=true;
                                pq.push({-abs(A[u]-B[u]),u});
                        }
                }

                for(auto x:del) {
                        calc[x]=false;
                        cnt--;
                }
        }

        return ans;
}