#define _CRT_SECURE_NO_WARNINGS
#include "closing.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen(".out", "w", stdout);
ll gcd(ll a, ll b)
{
if (a == 0 || b == 0) {
return max(a, b);
}
if (a <= b) {
return gcd(a, b % a);
}
else {
return gcd(a % b, b);
}
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
const int N = 200005;
const ll oo = 1000000000000000000, MOD = 1000000007;
vector<pair<int,ll>> g[N];
ll ans[3][N];
void dfs(int u, int ty,int p,ll sum) {
for (pair<int, ll> num : g[u]) {
if (num.fr != p) {
ans[ty][num.fr] = sum + num.sc;
dfs(num.fr, ty, u, sum + num.sc);
}
}
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U,
std::vector<int> V, std::vector<int> W) {
int n = N, x = X, y = Y;
ll k = K;
if (x >= y) {
while (1) {
}
}
for (int i = 0; i < n; ++i) {
g[i].clear();
}
for (int i = 0; i < n; ++i) {
ans[0][i] = ans[1][i] = 0;
}
for (int i = 0; i < n - 1; ++i) {
g[U[i]].pb({ V[i],W[i] });
g[V[i]].pb({ U[i],W[i] });
}
dfs(x, 0, -1, 0);
dfs(y, 1, -1, 0);
int pat = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int rx = min(x + i - 1, n - 1), ly = max(y - j + 1, 0), qan = 0;
ll sm = 0;
for (int ind = 0; ind < n; ++ind) {
if (ind >= x && ind <= rx && ind>=ly && ind<=y) {
sm += max(ans[0][ind], ans[1][ind]);
qan += 2;
}
else {
if (ind >= ly && ind <= y) {
sm += ans[1][ind];
if (ly == y) {
if (ans[1][ind] != 0) {
while (1) {
}
}
}
++qan;
}
if (ind >= x && ind <= rx) {
sm += ans[0][ind];
if (rx == x) {
if (ans[0][ind] != 0) {
while (1) {
}
}
}
++qan;
}
}
}
if (x == 254 && y == 499 && i == 1 && j == 1) {
}
qan += max(x - ly, 0);
qan += max(rx - y, 0);
ll mnac = k - sm;
if (mnac >= 0) {
sm = 0;
int minchev = min(x, ly) - 1;
ll sm1 = 0;
while (minchev >= 0 && sm1+ans[0][minchev]<=mnac) {
sm1 += ans[0][minchev];
--minchev;
++qan;
}
++minchev;
pat = max(pat, qan);
for (int ind = max(y, rx) + 1; ind < n; ++ind) {
mnac -= ans[1][ind];
if (mnac < 0) {
break;
}
while (minchev < min(x, ly) && sm1>mnac) {
sm1 -= ans[0][minchev];
--qan;
++minchev;
}
++qan;
pat = max(pat, qan);
}
}
}
}
/*if (pat == 0) {
cout << "GTAV" << " " << x << " " << y << " " << n << " " << k << endl;
}*/
return pat;
}
