#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;
int n;
vector<pair<int, int> > g[N];
void dfs0(int x, int p, vector<ll>& d)
{
if (x == p)
d[x] = 0;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
d[h] = d[x] + g[x][i].se;
dfs0(h, x, d);
}
}
bool dfs1(int x, int p, int y, vector<int>& v)
{
v.push_back(x);
if (x == y)
return true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
if (dfs1(h, x, y, v))
return true;
}
v.pop_back();
return false;
}
bool c[N];
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
n = N;
for (int i = 0; i <= n + 1; ++i)
{
c[i] = false;
g[i].clear();
}
for (int i = 0; i < n - 1; ++i)
{
int x = U[i];
int y = V[i];
int z = W[i];
g[x].push_back(m_p(y, z));
g[y].push_back(m_p(x, z));
}
vector<ll> dX(n);
dfs0(X, X, dX);
vector<ll> dY(n);
dfs0(Y, Y, dY);
vector<int> v;
dfs1(X, X, Y, v);
int ans = 0;
{
vector<ll> w;
for (int x = 0; x < n; ++x)
w.push_back(min(dX[x], dY[x]));
sort(all(w));
ll k = K;
for (int i = 0; i < n; ++i)
{
if (k >= w[i])
{
k -= w[i];
++ans;
}
}
}
ll k = K;
int pans = 0;
vector<ll> w1;
for (int i = 0; i < sz(v); ++i)
{
if (k >= min(dX[v[i]], dY[v[i]]))
{
k -= min(dX[v[i]], dY[v[i]]);
++pans;
w1.push_back(max(dX[v[i]], dY[v[i]]) - min(dX[v[i]], dY[v[i]]));
}
c[v[i]] = true;
}
if (pans != sz(v))
return ans;
vector<pair<ll, int> > w;
for (int x = 0; x < n; ++x)
{
if (c[x])
continue;
w.push_back(m_p(min(dX[x], dY[x]), x));
}
sort(all(w));
for (int i = -1; i < sz(w); ++i)
{
if (i >= 0)
{
int x = w[i].se;
c[x] = true;
k -= min(dX[x], dY[x]);
++pans;
w1.push_back(max(dX[x], dY[x]) - min(dX[x], dY[x]));
if (k < 0)
break;
}
vector<ll> w2;
for (int x = 0; x < n; ++x)
{
if (!c[x])
{
w2.push_back(max(dX[x], dY[x]));
}
}
sort(all(w2));
sort(all(w1));
vector<ll> p1, p2;
p1.push_back(0);
for (int i = 0; i < sz(w1); ++i)
{
p1.push_back(p1.back() + w1[i]);
}
p2.push_back(0);
for (int i = 0; i < sz(w2); ++i)
{
p2.push_back(p2.back() + w2[i]);
}
for (int i = 0; i < sz(w1); ++i)
{
for (int j = 0; j < sz(w2); ++j)
{
if (k >= p1[i] + p2[j])
ans = max(ans, pans + i + 2 * j);
}
}
}
return ans;
}
