#include "closing.h"
#include <set>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<__int128,int>
#define ll __int128
int const N=2e5+10;
vector<pair<int,int>>nei[N]={};
__int128 dist[3][N]={};
__int128 dp[2*N]={};
int par[N]={};
bool wy[N]={};
vector<int>pth;
void bfs(int u,bool ind)
{
dist[ind][u]=0;
set<pair<__int128,int>>s;
s.insert({0,u});
if (ind==0)
par[u]=-1;
while (s.size())
{
__int128 u=(*begin(s)).second,w=(*begin(s)).first;
s.erase(*begin(s));
if (dist[ind][u]!=w) continue;
for (auto [i,w1]:nei[u])
{
if (dist[ind][i]>w+w1)
{
if (ind==0)
par[i]=u;
dist[ind][i]=w+w1;
s.insert({dist[ind][i],i});
}
}
}
}
vector<int>s;
int n;
void dfs(int u)
{
for (auto [i,w1]:nei[u])
{
if (wy[i]||i==par[u]) continue;
s.push_back(i);
dfs(i);
}
}
int fd(__int128 lef,int i,int j)
{
s={};
for (int k=0;k<pth.size();k++)
dfs(pth[k]);
for (int i=0;i<=2*n;i++)
dp[i]=1e18+10;
dp[0]=0;
for (auto i:s)
{
for (int j=2*N;j>=1;j--)
{
dp[j]=min(dp[j],dp[j-1]+dist[0][i]);
if (j>1)
dp[j]=min(dp[j],dp[j-2]+dist[1][i]);
}
}
int cur=0;
for (int i=2*n;i>=0;i--)
{
if (dp[i]<=lef)
{
cur=i;
break;
}
}
return cur;
}
int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W)
{
n=N;
pth={};
for (int i=0;i<N;i++)
{
wy[i]=0;
nei[i]={};
}
for (int i=0;i<U.size();i++)
{
nei[U[i]].push_back({V[i],W[i]});
nei[V[i]].push_back({U[i],W[i]});
}
for (int i=0;i<N;i++)
dist[0][i]=dist[1][i]=1e18;
bfs(X,0);
bfs(Y,1);
int ans=0;
multiset<__int128>s;
for (int i=0;i<N;i++)
{
s.insert(dist[0][i]);
s.insert(dist[1][i]);
if (dist[0][i]>dist[1][i])
swap(dist[0][i],dist[1][i]);
}
int f=Y;
while (f!=-1)
{
pth.push_back(f);
f=par[f];
}
for (auto i:pth)
wy[i]=1;
reverse(begin(pth),end(pth));
vector<__int128>pre={0},pre1={0};
int sz=pth.size();
for (auto i:pth)
{
pre.push_back(pre.back()+dist[1][i]);
pre1.push_back(pre1.back()+dist[0][i]);
}
__int128 cur=0;
while (s.size())
{
__int128 w=(*begin(s));
if (cur+w>k)
break;
ans++;
cur+=w;
s.erase(begin(s));
}
s={};
for (int i=0;i<sz;i++)
{
for (int j=i;j<sz;j++)
{
__int128 init=pre[j+1]-pre[i];
init+=pre1[i];
if (j+1<=sz)
init+=(pre1[sz]-pre1[j+1]);
if (init>k) continue;
int g=fd(k-init,i,j);
int tr=(j-i+1)+sz+g;
ans=max(ans,tr);
}
}
return ans;
}
