#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
typedef long long ll;
const ll INF = 4e18;
int n;
int x, y; ll k;
ll dp[MAXN][2 * MAXN];
ll mindist[MAXN], maxdist[MAXN];
vector<int> curpath;
bool forced[MAXN];
vector<pair<int, ll>> adj[200005];
priority_queue<ll> pq;
void dfs1(int node, int parent, ll curdist) {
pq.push(-curdist);
for (auto a : adj[node])
if (a.first != parent)
dfs1(a.first, node, a.second + curdist);
}
void dfs2(int node, int parent, ll curdist) {
mindist[node] = min(mindist[node], curdist);
maxdist[node] = max(maxdist[node], curdist);
for (auto a : adj[node])
if (a.first != parent)
dfs2(a.first, node, a.second + curdist);
}
bool dfs3(int node, int parent) {
curpath.push_back(node);
if (node == y) {
for (auto a : curpath)
forced[a] = true;
return true;
}
for (auto a : adj[node])
if (a.first != parent)
if (dfs3(a.first, node))
return true;
curpath.pop_back();
return false;
}
int solve_brute() {
while (pq.size())
pq.pop();
dfs1(x, -1, 0); dfs1(y, -1, 0);
int ans = 0;
ll cost = 0;
while (cost <= k && pq.size()) {
ll cur = -pq.top(); pq.pop();
if (cost + cur <= k)
ans ++, cost += cur;
else break;
}
return ans;
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
memset(forced, false, sizeof(forced));
n = N;
x = X; y = Y; k = K;
for (int i = 0; i < n - 1; i ++) {
int a, b; ll c;
a = U[i]; b = V[i]; c = W[i];
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
if (N > MAXN) {
int ans = solve_brute();
for (int i = 0; i < n; i ++)
adj[i].clear();
return ans;
}
for (int i = 0; i <= N; i ++)
for (int j = 0; j <= 2 * N; j ++)
dp[i][j] = INF;
for (int i = 0; i < n; i ++)
maxdist[i] = 0, mindist[i] = INF;
curpath.clear();
dfs2(x, -1, 0); dfs2(y, -1, 0);
dfs3(x, -1);
dp[0][0] = 0;
for (int i = 1; i <= n; i ++) {
// do not take
if (!forced[i])
for (int j = 0; j <= 2 * n; j ++)
dp[i][j] = min(dp[i][j], dp[i - 1][j]);
// take once
for (int j = 1; j <= 2 * n; j ++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + mindist[i - 1]);
}
// take twice
for (int j = 2; j <= 2 * n; j ++) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 2] + maxdist[i - 1]);
}
}
int best = 0;
for (int j = 0; j <= 2 * n; j ++)
if (dp[n][j] <= k)
best = max(best, j);
best = max(best, solve_brute());
for (int i = 0; i < n; i ++)
adj[i].clear();
return best;
}
