#include "closing.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
void dfs(int st, vector<array<int,2>>g[], int p, long long dist[], long long d){
dist[st]=d;
for(array<int,2>e:g[st]){
if(e[0]==p)
continue;
dfs(e[0],g,st,dist,d+e[1]);
}
}
vector<int>xypath;
void dfsxy(int st, vector<array<int,2>>g[], int p, vector<int>&path, int y){
path.push_back(st);
if(st==y){
xypath.clear();
for(int i : path){
xypath.push_back(i);
}
}
for(array<int,2>e : g[st]){
if(e[0]==p)
continue;
dfsxy(e[0],g,st,path,y);
}
path.pop_back();
}
int max_score(int n, int x, int y, long long k, vector<int> u, vector<int> v, vector<int> w) {
vector<array<int,2>>g[n];
int m = u.size();
for(int i = 0;i<m;i++){
g[u[i]].push_back({v[i],w[i]});
g[v[i]].push_back({u[i],w[i]});
}
long long distx[n], disty[n];
dfs(x,g,-1,distx,0);
dfs(y,g,-1,disty,0);
long long cost1[n],cost2[n];
for(int i = 0;i<n;i++){
cost1[i]=min(distx[i],disty[i]);
cost2[i]=max(distx[i],disty[i])-cost1[i];
}
vector<int>pt;
dfsxy(x,g,-1,pt,y);
//case 1:
int ans1 = 0;
//only till level 1.
priority_queue<long long,vector<long long>,greater<long long>>pq;
for(int i = 0;i<n;i++){
pq.push(cost1[i]);
}
long long curk = 0;
while(curk<=k&&pq.size()){
long long a = pq.top();
pq.pop();
if(curk+a>k)
break;
ans1++;
curk+=a;
}
//case 2:
bool man[n];
fill(man,man+n,0);
for(int i : xypath){
man[i]=1;
}
long long dp[n][2*n+1];
// Initialize all states to a large value (invalid)
for (int i = 0; i < n; i++) {
fill(dp[i], dp[i] + 2*n + 1, (long long)2e18);
}
// Base case for the first bag (i=0)
if (man[0]) {
// Mandatory: must take at least one item
dp[0][1] = cost1[0];
dp[0][2] = cost1[0] + cost2[0]; // Fixed: use cost2[0]
} else {
// Non-mandatory: can skip, take one, or take two
dp[0][0] = 0;
dp[0][1] = cost1[0];
dp[0][2] = cost1[0] + cost2[0]; // Fixed: use cost2[0]
}
// Fill DP table for bags 1 to n-1
for (int i = 1; i < n; i++) {
for (int j = 0; j <= 2*n; j++) { // Include j=0
if (man[i]) {
// Mandatory bag: must take at least one item
if (j >= 1) {
// Take one item
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost1[i]);
}
if (j >= 2) {
// Take two items
dp[i][j] = min(dp[i][j], dp[i-1][j-2] + cost1[i] + cost2[i]);
}
} else {
// Non-mandatory bag: skip, take one, or take two
dp[i][j] = min(dp[i][j], dp[i-1][j]); // Skip
if (j >= 1) {
// Take one item
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + cost1[i]);
}
if (j >= 2) {
// Take two items
dp[i][j] = min(dp[i][j], dp[i-1][j-2] + cost1[i] + cost2[i]);
}
}
// Cap the value to avoid overflow
if (dp[i][j] > (long long)2e18) {
dp[i][j] = (long long)2e18;
}
}
}
// Find the maximum items from the last row (all bags processed)
int ans2 = 0;
for (int j = 0; j <= 2*n; j++) {
if (dp[n-1][j] <= k) {
ans2 = max(ans2, j);
}
}
return max(ans1,ans2);
}
