#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
int val, j, id;
bool operator < (const thing b) const {
if (val != b.val) return val < b.val;
if (j != b.j) return j < b.j;
return id < b.id;
}
};
const int maxn = 2e5 + 5, INF = 2e18 + 10;
int n, X, Y, k, D;
vector<pair<int,int>> adj[maxn];
int dist[maxn][2], state[maxn];
int cost1[maxn], cost2[maxn];
void dfs(int u, int j) {
for (auto [v, w]:adj[u]) if (dist[v][j] == -1) {
dist[v][j] = dist[u][j] + w;
dfs(v, j);
}
}
map<int, vector<pair<int,int>>> mp;
set<pair<int,int>> s1, s2;
int ans, added, curans;
void update(int u, int x) {
if (state[u] == 1) {
s1.erase({cost1[u], u});
} else if (state[u] == 2) {
s2.erase({cost2[u], u});
} else if (state[u] == 3) {
added -= cost1[u];
curans--;
} else if (state[u] == 4) {
added -= cost2[u];
curans -= 2;
}
state[u] = x;
// cout << u << " " << cost1[u] << " " << cost2[u] << endl;
if (x == 1) {
s1.insert({cost1[u], u});
} else if (x == 2) {
s2.insert({cost2[u], u});
} else if (x == 3) {
added += cost1[u];
curans++;
} else if (x == 4) {
added += cost2[u];
curans += 2;
}
}
vector<pair<int,int>> ord;
int qry() {
if (added > k) return 0;
vector<int> S1 = {0};
for (auto [x, i]:s1) S1.push_back(x);
for (int i=1;i<S1.size();i++) S1[i] += S1[i-1];
int cnt = 0, val = 0;
int mx = upper_bound(S1.begin(), S1.end(), k - added) - S1.begin() - 1;
for (auto [x, i]:s2) {
cnt += 2, val += x;
if (added + val <= k) mx = max(cnt + (int)(upper_bound(S1.begin(), S1.end(), k - added - val) - S1.begin() - 1), mx);
}
return mx;
}
int32_t max_score(int32_t N, int32_t XX, int32_t YY, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
n = N, X = XX, Y = YY, k = K * 2;
for (int i=0;i<n;i++) adj[i].clear();
for (int i=0;i<U.size();i++) {
adj[U[i]].push_back({V[i], W[i] * 2});
adj[V[i]].push_back({U[i], W[i] * 2});
}
for (int i=0;i<n;i++) for (int j=0;j<=1;j++) dist[i][j] = -1;
dist[X][0] = 0;
dfs(X, 0);
dist[Y][1] = 0;
dfs(Y, 1);
D = dist[Y][0];
mp.clear();
ord.clear();
while (s1.size()) s1.erase(s1.begin());
while (s2.size()) s2.erase(s2.begin());
for (int i=0;i<n;i++) {
cost1[i] = min(dist[i][0], dist[i][1]);
cost2[i] = max(dist[i][0], dist[i][1]);
int del = cost2[i] - cost1[i];
mp[del].push_back({cost1[i], i});
state[i] = 0;
ord.push_back({cost2[i], i});
}
sort(ord.begin(), ord.end());
added = 0, curans = 0;
for (int i=0;i<n;i++) update(i, 1);
ans = qry();
for (int i=0;i<n;i++) {
if (cost1[i] + cost2[i] == D) update(i, 3);
else update(i, 1);
}
for (auto [x, i]:ord) {
update(i, 4);
if (added <= k) ans = max(qry() + curans, ans);
}
return ans;
}
