#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;

struct Option{
    ll a, b;
    int node;
    bool operator < (const Option & other) const{
        return b < other.b;
    }
};

int nodeNum, cityA, cityB;
ll lim;
vector <pii> edge[MAX];
bool onPath[MAX];
ll dist[MAX][2];
int ans;

vector <ll> v;
vector <Option> 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;
    
    v.clear();
    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
    onPath[cur] |= (cur == cityB);
    for (pii nex : edge[cur]){
        if (nex.node == par) continue;
        dist[nex.node][which] = dist[cur][which] + nex.wei;
        dfs(nex.node, cur, which);
        onPath[cur] |= onPath[nex.node];
    }
}

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

void noOverlap(){ // situation with no overlap
    for (int i = 0; i < nodeNum; i++)
        v.push_back(min(dist[i][0], dist[i][1]));
    sort(v.begin(), v.end());
    ll sum = 0;
    for (int i = 0; i < nodeNum; i++){
        sum += v[i];
        if (sum > lim) return;
        //cout << sum << " " << i << " \n";
        ans = max(ans, i+1);
    }
}

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({min(dist[i][0], dist[i][1]), max(dist[i][0], dist[i][1]), i});
        if (!onPath[i]) ms.insert(opt.back().a); // have to choose if it's between
        curCost += opt.back().a;
        curAns++;
    }
    moveBack();
    if (curCost > lim) return;
    ans = max(ans,curAns);
    //if (SZ(ms) != nodeNum) return;
    
    sort(opt.begin(), opt.end()); // sort by max distance

    for (Option o : opt){ // each node before o -> reachable to at least one city
        if (!onPath[o.node]){
            auto it = ms.find(o.a);
            if (it != ms.end()) ms.erase(it); // already chose
            else { // forced to choose now
                curAns++;
                curCost += o.a;
            }
        }
        ms.insert(o.b-o.a);
        curCost += o.b-o.a;
        curAns++;
        moveBack();
        if (curCost > lim) return;
        ans = max(ans, curAns);
        //cout << curCost << "\n";
    }
}

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);
    
    noOverlap();
    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/ccrfrqZt.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCUk5qq.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status