#include <bits/stdc++.h>
#define ll long long
#define SZ(X) (int)(X.size())
#define MAX 200005
#define pii pair <int,int>
#define node first
#define wei second
using namespace std;

int caseNum;
int nodeNum, cityA, cityB;
ll lim;
vector <pii> edge[MAX];
ll dist[MAX][2];
int ans;
int a, b, c;

vector <pii> opt; // b (cost for reachable from both), a (cost for reachable from one)
multiset <ll, greater <ll>> ms; // chosen costs
ll curCost;
int curAns;

void reset(){
    for (int i = 0; i < nodeNum; i++){
        edge[i].clear();
        dist[i][0] = dist[i][1] = 0;
    }
    ans = 0;
    
    opt.clear();
    ms.clear();
    curCost = 0;
    curAns = 0;
}

void dfs(int cur, int par, bool which){ // for each node, find distance from the two cities
    for (pii nex : edge[cur]){
        if (nex.node == par) continue;
        dist[nex.node][which] = dist[cur][which] + nex.wei;
        dfs(nex.node, cur, which);
    }
}

void moveBack(){
    while (!ms.empty() && curCost > lim){
        curCost -= *ms.begin();
        curAns--;
        ms.erase(ms.begin());
    }
}

void msDelete(ll val){
    auto it = ms.find(val);
    if (it != ms.end()) ms.erase(it);
}

void enumOverlap(){ // check options for overlap
    for (int i = 0; i < nodeNum; i++){ // assume each node -> reachable to at most one city
        opt.push_back({max(dist[i][0], dist[i][1]), min(dist[i][0], dist[i][1])});
        ms.insert(opt.back().second);
        curCost += opt.back().second;
        curAns++;
    }
    moveBack();
    ans = curAns;
    /*sort(opt.begin(), opt.end()); // sort by max distance

    for (pii o : opt){ // each node before o -> reachable to at least one city
        curCost += o.second;
        curAns++;
        msDelete(o.second);
        ms.insert(o.first-o.second);
        moveBack();
        if (curCost > lim) return;
        ans = max(ans, curAns);
    }*/
}

int max_score(int N, int A, int B, ll limit, vector <int> U, vector <int> V, vector <int> W){
    nodeNum = N;
    cityA = A;
    cityB = B;
    lim = limit;
    
    reset();
    for (int i = 0; i < nodeNum-1; i++){
        edge[U[i]].push_back({V[i], W[i]});
        edge[V[i]].push_back({U[i], W[i]});
    }
    dfs(cityA, -1, 0);
    dfs(cityB, -1, 1);

    enumOverlap();
    
    return ans;
}


int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << max_score(4, 0, 3, 20, {0, 1, 2}, {1, 2, 3}, {18, 1, 19}) << "\n";
    
    cout << max_score(7, 0, 2, 10,
                      {0, 0, 1, 2, 2, 5}, {1, 3, 2, 4, 5, 6}, {2, 3, 4, 2, 5, 3}) << "\n";
     
    return 0;
}

/usr/bin/ld: /tmp/ccKHaW3Q.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccVKPPWR.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status