#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const long long INF = 1e18;
int onp[maxn];
long long depX[maxn], depY[maxn];
vector<pair<int, int>> g[maxn];
void dfsX(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depX[v.first] = depX[x] + v.second;
dfsX(v.first, x);
}
}
void dfsY(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depY[v.first] = depY[x] + v.second;
dfsY(v.first, x);
}
}
long long solve1(int n, long long k)
{
vector<long long> vec;
vec.insert(vec.end(), depX, depX + n);
vec.insert(vec.end(), depY, depY + n);
sort(vec.begin(), vec.end());
long long crr = 0;
for (int i = 0; i < vec.size(); i++)
{
crr += vec[i];
if (crr > k)
return i;
}
return vec.size();
}
vector<int> path;
bool dfs_path(int x, int endp, int p = -1)
{
if (x == endp)
return (onp[x] = true);
for (auto v : g[x])
{
if (v.first == p)
continue;
onp[x] |= dfs_path(v.first, endp, x);
}
return onp[x];
}
vector<long long> vec1, vec2;
void dfs_gen(int x, int p, long long cnst)
{
long long val;
if (p == -1)
val = 0;
else
val = min(depX[x], depY[x]);
if (val > cnst)
vec2.push_back(val);
else
vec1.push_back(val);
for (auto v : g[x])
{
if (v.first == p || onp[v.first])
continue;
dfs_gen(v.first, x, cnst);
}
}
vector<long long> v1;
vector<pair<long long, long long>> v2;
vector<long long> mn;
int ptr;
long long mx, sum;
long long solve_v2(long long k)
{
if (k < 0)
return -INF;
while (ptr < v2.size() && v2[ptr].first + sum <= k)
{
mx = max(mx, v2[ptr].first - v2[ptr].second);
sum += v2[ptr].first;
ptr++;
}
if (ptr == v2.size())
return 2 * ptr;
else
{
if (sum - mx + v2[ptr].first <= k || sum + mn[ptr] <= k)
return 2 * ptr + 1;
else
return 2 * ptr;
}
}
long long solve2(int n, long long k, int x, int y)
{
dfs_path(x, y);
long long re = 0;
v1.clear();
v2.clear();
ptr = 0;
mx = -INF;
sum = 0;
for (int i = 0; i < n; i++)
{
if (onp[i])
{
k -= min(depX[i], depY[i]);
vec1.clear();
vec2.clear();
long long inc = abs(depX[i] - depY[i]);
dfs_gen(i, -1, inc);
for (auto v : vec1)
{
v1.push_back(v);
v1.push_back(inc);
}
for (auto v : vec2)
{
v2.push_back({v + inc, v});
}
// cout << i << endl;
// for(auto v: knapsack[len])cout << v << " ";
// cout << endl;
}
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
if (!v2.empty())
{
mn.resize(v2.size());
for (int i = v2.size() - 1; i >= 0; i--)
{
mn[i] = v2[i].second;
if (i + 1 < v2.size())
mn[i] = min(mn[i], mn[i + 1]);
}
}
// cout << "left " << k << endl;
if (k < 0)
return 0;
k -= accumulate(v1.begin(), v1.end(), 0LL);
re = max(re, solve_v2(k) + (long long)v1.size());
for (int i = v1.size() - 1; i >= 0; i--)
{
k += v1[i];
re = max(re, solve_v2(k) + i);
}
return re;
}
void reset(int n)
{
for (int i = 0; i < n; i++)
{
g[i].clear();
onp[i] = 0;
}
path.clear();
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
reset(N);
for (int i = 0; i < N - 1; i++)
{
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
depX[X] = 0;
depY[Y] = 0;
dfsX(X);
dfsY(Y);
long long ans = max(solve1(N, K), solve2(N, K, X, Y));
return ans;
}
