// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pp push
vector<vector<pair<int,ll>>> graph;
vector<bool> vis;
vector<ll> seg1,seg2;

struct node{
	ll t;
	int x, cnt = 0;
	bool operator<(const node &b) const
    {
        return t < b.t;
    }
    bool operator>(const node &b) const
    {
        return b < (*this);
    }
};

int greedy(int mx, ll k, ll mdist) {
    //cout <<"1\n";
	int N = (int)vis.size(), ans = 0;
	vector<int> cnt(N, 0);
	priority_queue<node, vector<node>, greater<node>> pqa, pqb;
    //cout <<"1\n";
	for (int i = 0; i < N; i ++) {
		if (mx == 2 && seg1[i] + seg2[i] == mdist) {// case 1 a's
			ans++;
			cnt[i] ++;
			k -= min(seg1[i], seg2[i]);
            pqa.pp({abs(seg1[i] - seg2[i]), i, 1});
		} else  { 
			pqa.pp({min(seg1[i], seg2[i]), i ,0});
			if (mx == 2 ) {// case 2 the b's
				pqb.pp({max(seg1[i], seg2[i]), i , 0});
			}
		}
	}
    //cout <<"1\n";
	 auto get_top = [](priority_queue<node, vector<node>, greater<node>> &pq) -> node
    {
        return pq.empty() ? node{(long long)1e18, 0} : pq.top();
    };

    auto reduce = [&cnt, &mx, &k](priority_queue<node, vector<node>, greater<node>> &pq) -> void
    {
        while (!pq.empty() && (cnt[pq.top().x] != pq.top().cnt || k < pq.top().t))
        {
            pq.pop();
        }
    };
    //cout <<"1\n";
    while (!pqa.empty() || !pqb.empty())
    {
        reduce(pqa);
        reduce(pqb);
        if (pqa.empty() && pqb.empty())
            break;
        node one1 = get_top(pqa), one2;
        if (!pqa.empty())
        {
            pqa.pop();
            cnt[one1.x]++;
            reduce(pqa);
            cnt[one1.x]--;
            one2 = get_top(pqa);
        }
        node two = get_top(pqb);
        if (pqb.empty() || one1.t + one2.t < two.t)
        {
            k -= one1.t;
            ans++;
            cnt[one1.x]++;
            if (mx == 2 && cnt[one1.x] == 1)
            {
                pqa.pp({abs(seg1[one1.x] - seg2[one1.x]), one1.x, 1});
            }
        }
        else
        {
            pqa.pp(one1);
            k -= min(seg1[two.x], seg2[two.x]);
            ans++;
            cnt[two.x]++;
            pqa.pp({abs(seg1[two.x] - seg2[two.x]), two.x, 1});
            pqb.pop();
        }
    }
    //cout <<"1\n";
    return k < 0 ? 0 : ans;
}
void ddd(vector<ll>& cseg, int node, ll dist) {
	vis[node] = true;
	cseg[node] = dist;
	for (auto [c,w] : graph[node]) {
		if (!vis[c]) {
			ddd(cseg, c, dist + (ll)w);
		}
	}
}
int max_score(int N, int X, int Y, ll k, vector<int> U, vector<int> V, vector<ll> W) {
    graph.resize(N);
	seg1.resize(N);
	seg2.resize(N);
    //cout <<"1\n";
    for (int i = 0; i < N - 1; i++) {
		graph[U[i]].pb({V[i], W[i]});
		graph[V[i]].pb({U[i], W[i]});
	}
	//travel through "a" values for X
    //cout <<"1\n RTE LMFAO";
    vis.assign(N,false);
	ddd(seg1, X, (ll)0);
	//travel through "a" values for Y
	vis.assign(N,false);
    //cout <<"1\n";
    ddd(seg2, Y, (ll)0);


	//max of b's and a's for X->Y
    //cout <<"1\n";
    return max(greedy(2, k, seg1[Y]), greedy(1, k, seg1[Y]));
    //return 1;
}
// void run() {
// 	int n,x,y;
// 	ll k;
// 	cin >> n >> x >> y >> k;
// 	vector<int> u(n),v(n),w(n);
// 	for (int i = 0; i < n-1; i ++) {
// 		cin >> u[i] >> v[i] >> w[i];
//         // u[i]--;
//         // v[i]--;
// 	}
// 	cout << max_score(n,x,y,k,u,v,w) << "\n";
// }
// int main() {
// 	// ios_base::sync_with_stdio(false);
// 	// cin.tie(0);
// 	int t;
// 	cin >> t;
// 	while(t--) {
//         cout <<"running\n";
// 		run();
//         graph.clear();
//         vis.clear();
//         seg1.clear();
//         seg2.clear();
// 	}
// }

answer.code: In function ‘void ddd(std::vector<long long int>&, int, long long int)’:
answer.code:102:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  102 |         for (auto [c,w] : graph[node]) {
      |                   ^
/usr/bin/ld: /tmp/ccKyISMk.o: in function `main':
implementer.cpp:(.text.startup+0x744): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status