// linear network
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, a, b;
ll k;
vector<int> w;
vector<ll> minX, minY;
vector<vector<pair<int, int>>> tree;
int solve_line() {
return -1;
}
void dfs(int node, bool a, int par = -1, ll dep = 0LL) {
if (!a) minX[node] = dep;
else minY[node] = dep;
for (auto [next, c]: tree[node]) {
if (next == par) continue;
dfs(next, a, node, dep + c);
}
}
int solve_line(int x, int y) {
int currS = 0;
for (int i = x+1; i < n; i++) {
minX[i] = minX[i-1] + w[i - 1];
}
for (int i = x-1; i >= 0; i--) {
minX[i] = minX[i+1] + w[i];
}
for (int i = y+1; i < n; i++) {
minY[i] = minY[i-1] + w[i - 1];
}
for (int i = y-1; i >= 0; i--) {
minY[i] = minY[i+1] + w[i];
}
vector<ll> minBoth(n, 0);
vector<ll> f, s;
for (int i = 0; i < n; i++) {
minBoth[i] = max(minX[i], minY[i]);
}
f = minX;
s = minY;
for (int i = 1; i < n; i++) {
minX[i] = minX[i-1] + minX[i];
minY[i] = minY[i-1] + minY[i];
minBoth[i] = minBoth[i-1] + minBoth[i];
}
int maxAns = 0;
for (int l = 0; l <= y; l++) {
for (int r = max(x, l); r < n; r++) { // (l, r) included in both
int ans = (r - l + 1) * 2;
ll cost = minBoth[r];
if (l > 0) cost -= minBoth[l-1];
if (y > r) {
cost += minY[y] - minY[r];
ans += (y - r);
}
if (l > x) {
cost += minX[l-1];
if (x > 0) cost -= minX[x-1];
ans += (l - x);
}
if (cost > k) continue;
int a = min(l-1, x-1), b = max(y+1, r+1);
while (cost <= k && (a >= 0 || b < n)) {
int nxt = 0;
if (a < 0) {
nxt = minY[b];
if (b > 0) nxt -= minY[b-1];
b++;
}
else if (b >= n) {
nxt = minX[a];
if (a > 0) nxt -= minX[a-1];
a--;
}
else {
int opt1 = minY[b], opt2 = minX[a];
if (a > 0) opt2 -= minX[a-1];
if (b > 0) opt1 -= minY[b-1];
if (opt2 <= opt1) {
a--;
nxt = opt2;
}
else {
b++;
nxt = opt1;
}
}
if (nxt + cost > k) break;
cost += nxt;
ans++;
}
maxAns = max(maxAns, ans);
}
}
int ans = 0;
vector<ll> sec;
for (int i = 0; i < n; i++) {
sec.push_back(min(f[i], s[i]));
}
sort(sec.begin(), sec.end());
for (auto cr: sec) {
if (cr <= k) {
k -= cr;
ans++;
}
}
maxAns = max(maxAns, ans);
return maxAns;
}
int max_score(int sz, int x, int y, ll l, vector<int> u, vector<int> v, vector<int> weights) {
n = sz;
tree.clear();
tree.resize(n);
k = l;
w = weights;
for (int i = 0; i < n-1; i++) {
//int xx = u[i];
tree[u[i]].push_back({v[i], w[i]});
tree[v[i]].push_back({u[i], w[i]});
}
minX.clear();
minX.assign(n, 0LL);
minY.clear();
minY.assign(n, 0LL);
bool line = true;
for (int i = 0; i < n-1; i++) {
if (v[i] != u[i] + 1) {
line = false;
break;
}
}
if (line) return solve_line(x, y);
else {
dfs(x, false);
dfs(y, true);
vector<ll> costs;
for (int i = 0; i < n; i++) {
costs.push_back(min(minX[i], minY[i]));
//costs.push_back(minY[i]);
}
sort(costs.begin(), costs.end());
int ans = 0;
int p = (int)costs.size();
for (int i = 0; i < p; i++) {
ll x = costs[i];
if (k >= x) {
ans++;
k -= x;
}
else break;
}
return ans;
}
}
/*
int main() {
cout << max_score(6, 1, 3, 5, {0, 1, 2, 3, 4}, {1, 2, 3, 4, 5}, {10, 1, 1, 1, 1}) << "\n";
}*/
