#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
vector < pair < int, ll > > adj[maxn];
ll dist[2][maxn];
int n;
void bfs(int s, ll arr[])
{
queue < int > q;
for (int i = 0; i < n; i ++)
arr[i] = -1;
arr[s] = 0;
q.push(s);
while(!q.empty())
{
int v = q.front();
q.pop();
for (pair < int, ll > nb : adj[v])
{
if (arr[nb.first] == -1)
{
arr[nb.first] = arr[v] + nb.second;
q.push(nb.first);
}
}
}
}
const ll inf = 1e18;
ll value[maxn];
ll dp[2][2][3010][3010 * 2], sub[maxn], temp[2][2][maxn * 2];
int used[maxn];
/**
*/
vector < int > st[maxn];
void dfs(int v, int t)
{
///cout << "dfs " << v << endl;
sub[v] = 1;
used[v] = 1;
if (t != v)
st[t].push_back(v);
for (int j = 0; j <= 2; j ++)
for (int d = 0; d < 2; d ++)
for (int z = 0; z < 2; z ++)
dp[d][z][v][j] = inf;
dp[0][0][v][0] = 0;
dp[1][0][v][1] = dist[0][v];
dp[0][1][v][1] = dist[1][v];
dp[1][1][v][2] = max(dist[0][v], dist[1][v]);
for (pair < int, ll > nb : adj[v])
{
if (used[nb.first])
continue;
dfs(nb.first, t);
int u = nb.first;
for (int i = 0; i <= (sub[u] + sub[v]) * 2; i ++)
for (int x = 0; x < 2; x ++)
for (int y = 0; y < 2; y ++)
temp[x][y][i]= inf;
for (int i = 0; i <= sub[v] * 2; i ++)
for (int j = 0; j <= sub[u] * 2; j ++)
for (int d = 0; d < 2; d ++)
for (int z = 0; z < 2; z ++)
for (int x = 0; x <= d; x ++)
for (int y = 0; y <= z; y ++)
{
temp[d][z][i + j] = min(temp[d][z][i + j], dp[d][z][v][i] + dp[x][y][u][j]);
}
for (int i = 0; i <= (sub[v] + sub[u]) * 2; i ++)
for (int x = 0; x < 2; x ++)
for (int y = 0; y < 2; y ++)
dp[x][y][v][i] = temp[x][y][i];
sub[v] += sub[u];
}
}
ll fp[3][3010][3010 * 2], tp[3010 * 2];
void unite(ll arr1[], int sz1, ll arr2[], int sz2, ll res[])
{
for (int i = 0; i <= (sz1 + sz2) * 2; i ++)
{
tp[i] = inf;
}
for (int i = 0; i <= sz1 * 2; i ++)
for (int j = 0; j <= sz2 * 2; j ++)
tp[i + j] = min(tp[i + j], arr1[i] + arr2[j]);
for (int i = 0; i <= (sz1 + sz2) * 2; i ++)
res[i] = tp[i];
}
vector < int > path;
bool get_path(int v, int p, int target)
{
if (v == target)
{
path.push_back(v);
return true;
}
for (pair < int, ll > nb : adj[v])
{
if (nb.first == p)
continue;
if (get_path(nb.first, v, target))
{
path.push_back(v);
return true;
}
}
return false;
}
int ans, loc[maxn];
ll td[3][3][maxn];
int max_score(int N, int X, int Y, long long K,
vector<int> U, vector<int> V, vector<int> W)
{
for (int i = 0; i < N; i ++)
{
dist[0][i] = dist[1][i] = 0;
adj[i].clear();
used[i] = 0;
value[i] = 0;
}
ans = 0;
n = N;
for (int i = 0; i < N - 1; i ++)
{
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
bfs(X, dist[0]);
bfs(Y, dist[1]);
path.clear();
get_path(Y, -1, X);
for (int cur : path)
used[cur] = 1;
for (int cur : path)
dfs(cur, cur);
vector < ll > vec;
for (int i = 0; i < N; i ++)
{
vec.push_back(dist[0][i]);
vec.push_back(dist[1][i]);
}
sort(vec.begin(), vec.end());
ll sum = 0;
for (int i = 0; i < vec.size(); i ++)
{
sum += vec[i];
if (sum > K)
break;
ans = max(ans, i + 1);
}
for (int id = (int)(path.size()) - 1; id >= 0; id --)
{
int ver = path[id];
loc[ver] = sub[ver];
for (int j = 0; j <= 2 * sub[ver]; j ++)
{
fp[2][ver][j] = dp[0][1][ver][j];
fp[1][ver][j] = dp[1][1][ver][j];
fp[0][ver][j] = dp[1][0][ver][j];
}
if (id + 1 == path.size())
continue;
for (int j = 0; j < 3; j ++)
{
for (int p = j; p < 3; p ++)
{
unite(fp[j][ver], loc[ver], fp[p][path[id + 1]], loc[path[id + 1]], td[j][p]);
/**for (int i = 0; i <= N * 2; i ++)
cout << td[j][p][i] << " ";
cout << endl;*/
}
}
///cout << "step " << ver << endl; for (int i = 0; i <= 2* (loc[ver] + loc[path[id + 1]]); i ++)
///cout << td[0][1][i] << endl;
for (int j = 0; j < 3; j ++)
{
for (int i = 0; i <= 2 * (loc[ver] + loc[path[id + 1]]); i ++)
fp[j][ver][i] = inf;
for (int p = j; p < 3; p ++)
{
for (int i = 0; i <= 2 * (loc[ver] + loc[path[id + 1]]); i ++)
{
fp[j][ver][i] = min(fp[j][ver][i], td[j][p][i]);
}
}
}
loc[ver] += loc[path[id + 1]];
}
for (int i = 0; i <= N * 2; i ++)
{
///cout << fp[0][path[0]][i] << " : " << i << endl;
if (fp[0][path[0]][i] <= K)
ans = max(ans, i);
}
for (int i = 0; i <= N * 2; i ++)
{
///cout << fp[1][path[0]][i] << " : " << i << endl;
if (fp[1][path[0]][i] <= K)
ans = max(ans, i);
}
return ans;
}
