#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 200005;
vector<pair<int, int>> v[N];
ll her[N], her1[N];
void Dfs(int g, int p, ll hh)
{
her[g] = hh;
for (auto to : v[g])
{
if (to.first != p)
{
Dfs(to.first, g, hh + to.second);
}
}
}
void Dfs1(int g, int p, ll hh)
{
her1[g] = hh;
for (auto to : v[g])
{
if (to.first != p)
{
Dfs1(to.first, g, hh + to.second);
}
}
}
ll maxher[N], maxherpref[N], herpref[N], her1pref[N];
int max_score(int n, int x, int y, long long k, vector<int> u1, vector<int> v1, vector<int> w1)
{
for (int i = 0; i < n - 1; i++)
{
v[v1[i]].push_back({ u1[i], w1[i] });
v[u1[i]].push_back({ v1[i], w1[i] });
}
Dfs(x, -1, 0);
Dfs1(y, -1, 0);
vector<ll> ans;
for (int i = 0; i < n; i++)
{
ans.push_back(her[i]);
ans.push_back(her1[i]);
maxher[i] = max(her[i], her1[i]);
if (i == 0)maxherpref[i] = maxher[i];
else maxherpref[i] = maxherpref[i - 1] + maxher[i];
if (i == 0)herpref[i] = her[i];
else herpref[i] = herpref[i - 1] + her[i];
if (i == 0)her1pref[i] = her1[i];
else her1pref[i] = her1pref[i - 1] + her1[i];
}
sort(ans.begin(), ans.end());
int qan = 0;
for (int i = 0; i < ans.size(); i++)
{
if (k - ans[i] >= 0)
{
qan++;
k -= ans[i];
}
}
for (int i = 0; i < n; i++)
{
v[i].clear();
her[i] = 0;
her1[i] = 0;
}
int obshians = qan;
for (int i = 0; i <= y; i++)
{
for (int j = max(x, i); j < n; j++)
{
ll ggum = 0;
int himikvaqan = (j - i + 1) * 2;
ggum = maxherpref[j];
if (i)ggum -= maxherpref[i - 1];
if (j < y)
{
ggum += her1pref[y];
ggum -= her1pref[j];
}
if (x < i)
{
ggum += herpref[i - 1];
ggum -= herpref[x];
}
int xx = x;
if (i < x)xx = i;
int yy = y;
if (y < j)yy = j;
ll kop = k;
kop -= ggum;
if (kop < 0)
continue;
vector<ll> vvv;
for (int h = 0; h < xx; h++)
{
vvv.push_back(her[h]);
}
for (int h = yy + 1; h < n; h++)
{
vvv.push_back(her1[h]);
}
sort(vvv.begin(), vvv.end());
for (i = 0; i < vvv.size(); i++)
{
if (kop - vvv[i] >= 0)
{
kop -= vvv[i];
himikvaqan++;
}
}
obshians = max(obshians, himikvaqan);
}
}
return obshians;
}
