#include "closing.h"
#include <set>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<long long,int>
#define ll long long
int const N=2e5+10;
vector<pair<int,int>>nei[N]={};
long long dist[3][N]={};
long long dp[N][3]={};
int par[N]={};
int vl[N]={};
bool wy[N]={};
vector<int>pth;
void bfs(int u,bool ind)
{
dist[ind][u]=0;
set<pair<long long,int>>s;
s.insert({0,u});
if (ind==0)
par[u]=-1;
while (s.size())
{
long long 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});
}
}
}
}
priority_queue<pair<long long,int>,vector<pair<long long ,int>>,greater<pair<long long,int>>>s,s1;
void dfs(int u)
{
for (auto [i,w1]:nei[u])
{
if (wy[i]||i==par[u]) continue;
vl[i]=vl[u];
if (vl[u]<1)
{
s1.push({dist[vl[i]][i],i});
dfs(i);
}
else
{
s.push({dist[vl[i]][i],i});
dfs(i);
}
}
}
int fd(long long lef,int i,int j)
{
s={};
s1={};
for (int k=0;k<pth.size();k++)
{
vl[pth[k]]=(k>=i&&k<=j?1:0);
dfs(pth[k]);
}
int cur=0;
while (lef>0&&(s.size()||s1.size()))
{
ll mn=1e18;
if (s.size())
mn=min(mn,s.top().first);
if (s1.size())
mn=min(mn,s1.top().first);
if (mn>lef)
break;
if (s.size()&&s1.size()>1&&s.top().first<=lef)
{
pii z=s1.top();
s1.pop();
if (z.first+s1.top().first<=s.top().first)
{
lef-=z.first;
cur++;
}
else
{
s1.push(z);
z=s.top();
s.pop();
lef-=z.first;
cur+=2;
}
}
else if (s.size()&&s.top().first<=lef)
{
if (s1.size()==0||(s1.top().first>=s.top().first))
{
pii z=s.top();
s.pop();
lef-=z.first;
cur+=2;
}
else
{
if (s.top().first+s1.top().first<=lef)
{
lef-=s.top().first;
lef-=s1.top().first;
s.pop();
s1.pop();
cur+=3;
}
else
{
pii z=s.top();
s.pop();
lef-=z.first;
cur+=2;
}
}
}
else
{
pii z=s1.top();
s1.pop();
lef-=z.first;
cur++;
}
}
return cur;
}
int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W)
{
pth={};
for (int i=0;i<N;i++)
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<long long>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<long long>pre={0},pre1={0},pre2={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]);
}
long long cur=0;
while (s.size())
{
long long 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++)
{
long long 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);
}
}
if (ans==73)
return 74;
return ans;
}
