#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
vector<pair<int, int>> graph[N];
bool visx[N];
ll lenghtX[N];
bool visy[N];
ll lenghtY[N];
void dfsX(int node){
visx[node] = true;
for(auto child: graph[node]){
if(!visx[child.first]){
lenghtX[child.first] = 1LL*child.second + 1LL*lenghtX[node];
dfsX(child.first);
}
}
return;
}
void dfsY(int node){
visy[node] = true;
for(auto child: graph[node]){
if(!visy[child.first]){
lenghtY[child.first] = 1LL*child.second + 1LL*lenghtY[node];
dfsY(child.first);
}
}
return;
}
int max_score(int n, int x, int y, ll k, std::vector<int> u,
std::vector<int> v, std::vector<int> w){
for(int i = 0; i<n-1; i++){
graph[u[i]].push_back({v[i], w[i]});
graph[v[i]].push_back({u[i], w[i]});
}
dfsX(x);
dfsY(y);
for(int i = 0; i<=n; i++){
visx[i] = 0;
visy[i] = 0;
}
multiset<pair<pair<ll, ll>, ll>> s;
s.insert({{0, x}, 1});
s.insert({{0, y}, 2});
ll sum = 0;
int cnt = 0;
while(s.size()>0){
auto it = s.begin();
int v = (*it).first.second;
ll wt = (*it).first.first;
int mark = (*it).second;
sum+= wt;
//cout<<sum<<" "<<v<<" "<<wt<<"\n";
if(sum<= k) cnt+=1;
else break;
s.erase(it);
if(s.find({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark}) != s.end()){
s.erase({{lenghtX[v]+ lenghtY[v] - wt, v}, 3-mark});
s.insert({{lenghtX[v]+ lenghtY[v] - 2*wt, v}, 3-mark});
}
if(mark == 1){
visx[v] = true;
for(auto u: graph[v]){
if(visx[u.first] == 0){
if(visy[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtY[u.first], u.first}, 1});
else s.insert({{lenghtX[u.first], u.first}, 1});
//visx[u.first] = true;
}
}
}
else{
visy[v] = true;
for(auto u: graph[v]){
if(visy[u.first] == 0){
if(visx[u.first]) s.insert({{max(lenghtX[u.first], lenghtY[u.first]) - lenghtX[u.first], u.first}, 2});
else s.insert({{lenghtY[u.first], u.first}, 2});
//visy[u.first] = true;
}
}
}
// for(auto x: s){
// cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"\n";
// }
// cout<<"\n";
}
for(int i = 0; i<=n; i++){
lenghtX[i] = 0;
lenghtY[i] = 0;
visx[i] = 0;
visy[i] = 0;
graph[i].clear();
}
return cnt;
}
// int main() {
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> N(Q), X(Q), Y(Q);
// std::vector<long long> K(Q);
// std::vector<std::vector<int>> U(Q), V(Q), W(Q);
// for (int q = 0; q < Q; q++) {
// assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q]));
// U[q].resize(N[q] - 1);
// V[q].resize(N[q] - 1);
// W[q].resize(N[q] - 1);
// for (int i = 0; i < N[q] - 1; ++i) {
// assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i]));
// }
// }
// fclose(stdin);
// std::vector<int> result(Q);
// for (int q = 0; q < Q; q++) {
// result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]);
// }
// for (int q = 0; q < Q; q++) {
// printf("%d\n", result[q]);
// }
// fclose(stdout);
// return 0;
// }
