#include "closing.h"
#define pb push_back
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int maxn = 2e5 + 10;
long long n, x, y, k;
vector < pair < int, int > > g[maxn];
long long distx[maxn], disty[maxn];
int used[maxn];
void dfsy(int beg, long long dep)
{
used[beg] = 1;
disty[beg] = min(disty[beg], dep);
for (auto &[to, w]: g[beg])
{
if(used[to])continue;
dfsy(to, dep + w);
}
}
void dfsx(int beg, long long dep)
{
used[beg] = 1;
distx[beg] = min(distx[beg], dep);
for (auto &[to, w]: g[beg])
{
if(used[to])continue;
dfsx(to, dep + w);
}
}
int p[maxn], a[maxn];
int st0, st1;
int is[maxn];
void dfs0(int beg, int par, int i)
{
if(beg == x || beg == y)
{
if(st0 == -1)st0 = beg;
else st1 = beg;
}
p[beg] = i;
a[i] = beg;
for (auto &[to, w]: g[beg])
{
if(par == to)continue;
dfs0(to, beg, i+1);
}
}
long long currdist[maxn];
long long dp[maxn], pre[maxn];
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N;
x = X;
y = Y;
k = K;
for (int i = 0; i < n; ++ i)
g[i].clear();
for (int i = 0; i < n-1; ++ i)
{
int from = U[i];
int to = V[i];
int t = W[i];
g[from].pb(make_pair(to, t));
g[to].pb(make_pair(from, t));
}
int endpoint = 0;
for (int i = 0; i < n; ++ i)
{
if(g[i].size() == 1)endpoint = i;
}
st0 = -1;
st1 = -1;
dfs0(endpoint, -1, 1);
x = p[st0];
y = p[st1];
for (int i = 0; i < n; ++ i)
distx[i] = 1e18+1;
for (int i = 0; i < n; ++ i)
disty[i] = 1e18+1;
for (int i = 0; i < n; ++ i)
used[i] = 0;
dfsx(st0, 0);
for (int i = 0; i < n; ++ i)
used[i] = 0;
dfsy(st1, 0);
long long ans = 0;
for (int prex = x; prex >= 1; prex --)
{
for (int suffx = x; suffx <= n; ++ suffx)
{
for (int prey = y; prey >= 1; prey --)
{
for (int suffy = y; suffy <= n; ++ suffy)
{
long long tokens = 0, want = 0;
for (int i = 1; i <= n; ++ i)
{
int in1= 0, in2 = 0;
if(i >= prex && i <= suffx)in1 = 1;
if(i >= prey && i <= suffy)in2 = 1;
if(in1 && in2)want += max(distx[a[i]], disty[a[i]]);
else if(in1)want += distx[a[i]];
else if(in2)want += disty[a[i]];
tokens += in1;
tokens += in2;
if(want > k)break;
}
if(want <= k)ans = max(ans, tokens);
}
}
}
}
return ans;
/*for (int pref = x; pref <= n; ++ pref) /// kym x
{
for (int suff = 1; suff <= y; ++ suff) /// kym y
{
for (int i = 0; i <= 2*n; ++ i)
{
dp[i] = 1e18+1;
pre[i] = 1e18+1;
}
dp[0] = 0;
for (int i = 1; i <= n; ++ i)
{
for (int j = 2*n; j >= 0; -- j)
{
if(dp[j] == 1e18+1)continue;
if(i <= pref && i >= suff && j < 2*n - 1)dp[j+2] = min(dp[j+2], pre[j] + max(distx[a[i]], disty[a[i]]));
if(i <= pref && j < 2*n)dp[j+1] = min(dp[j+1], pre[j]+distx[a[i]]);
if(i >= suff && j < 2*n)dp[j+1] = min(dp[j+1], pre[j]+disty[a[i]]);
}
pre[2*n] = dp[2*n];
for (int j = 2*n-1; j >= 0; -- j)
pre[j] = min(pre[j+1], dp[j]);
}
for (int i = 0; i <= 2*n; ++ i)
if(dp[i] <= k)ans = max(ans, i);
}
}
return ans;*/
}
