#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'
using namespace std;
typedef long long ll;
const int mx=3e3+12;
const int mxn=2e5+12;
vector<pair<int,ll>> g[mxn];
vector<int> ord;
ll dp[4][mx][mx*2];
int sz2[mx];
ll cost1[mxn];
ll cost2[mxn];
ll tmp[4][mx*2];
bool is[mx];
int sz[mx];
ll n,k,x,y;
void init(){
ord.clear();
for(int i=0;i<n+10;i++){
g[i].clear();
cost1[i]=cost2[i]=0;
is[i]=sz[i]=0;
sz2[i]=0;
tmp[0][i]=tmp[1][i]=tmp[2][i]=1e18+1;
for(int j=0;j<n*2+10;j++){
dp[0][i][j]=dp[1][i][j]=dp[2][i][j]=dp[3][i][j]=1e18+1;
}
}
}
int calc(){
vector<ll> a,b;
int ans=0;
for(int i=0;i<n;i++){
a.push_back(cost1[i]);
b.push_back(cost2[i]);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
for(int i=1;i<n;i++){
a[i]+=a[i-1];
}
for(int i=1;i<n;i++){
b[i]+=b[i-1];
}
for(int i=0;i<n;i++){
if(a[i]<=k || b[i]<=k){
ans=max(ans,i+1);
}
}
for(int i=n-1,j=-1;i>=0;i--){
while(j<n-1 && b[j+1]+a[i]<=k){
j++;
}
if(j!=-1 && a[i]+b[j]<=k){
ans=max(ans,i+j+2);
}
}
return ans;
}
void calc(int v,int p,ll d[]){
for(auto [to,w]:g[v]){
if(to!=p){
d[to]=d[v]+w;
calc(to,v,d);
}
}
}
bool path(int v,int p,int f){
if(v==f){
ord.push_back(v);
is[v]=1;
return 1;
}
for(auto [to,w]:g[v]){
if(to!=p && path(to,v,f)){
ord.push_back(v);
is[v]=1;
return 1;
}
}
return 0;
}
void dfs(int v,int p){
dp[0][v][0]=0;
dp[1][v][1]=cost1[v];
dp[2][v][1]=cost2[v];
dp[3][v][2]=max(cost1[v],cost2[v]);
sz[v]=1;
for(auto [to,w]:g[v]){
if(to==p || is[to])continue;
dfs(to,v);
for(int m=0;m<4;m++){
for(int i=0;i<=n*2;i++){
tmp[m][i]=dp[m][v][i];
}
}
for(int m=0;m<4;m++){
for(int m1=m;m1>=0;m1=((m1-1)&m)){
for(int x=1;x<=sz[v]*2;x++){
for(int y=0;y<=sz[to]*2;y++){
tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][to][y]);
}
}
if(!m1)break;
}
}
for(int m=0;m<4;m++){
for(int i=0;i<=n*2;i++){
dp[m][v][i]=tmp[m][i];
}
}
sz[v]+=sz[to];
}
}
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,k=K,x=X,y=Y;
for(int i=0;i<n;i++){
cost1[i]=cost2[i]=0;
g[i].clear();
}
for(int i=0;i<n-1;i++){
g[V[i]].push_back({U[i],W[i]});
g[U[i]].push_back({V[i],W[i]});
}
calc(x,-1,cost1);
calc(y,-1,cost2);
if(cost[y]>2*k){
return calc();
}
init();
for(int i=0;i<n-1;i++){
g[V[i]].push_back({U[i],W[i]});
g[U[i]].push_back({V[i],W[i]});
}
calc(x,-1,cost1);
calc(y,-1,cost2);
int ans=calc();
path(y,-1,x);
for(int i=ord.size()-1;i>=0;i--){
dfs(ord[i],-1);
}
for(int i=0;i<n;i++){
sz2[i]=sz[i];
}
for(int i=ord.size()-2;i>=0;i--){
int v=ord[i],u=ord[i+1];
for(int m=2;m<4;m++){
for(int i=0;i<n*2+10;i++){
tmp[m][i]=1e18+1;
}
}
for(int m=2;m<4;m++){
for(int m1=m;m1>1;m1=((m1-1)&m)){
for(int x=1;x<=sz[v]*2;x++){
for(int y=1;y<=sz[u]*2;y++){
tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][u][y]);
}
}
}
}
for(int m=2;m<4;m++){
for(int i=0;i<n*2+10;i++){
dp[m][v][i]=tmp[m][i];
}
}
sz[v]+=sz[u];
}
for(int i=0;i<ord.size()-1;i++){
int u=ord[i],v=ord[i+1];
for(int m=0;m<2;m++){
for(int i=0;i<n*2+10;i++){
tmp[m][i]=1e18+1;
}
}
int m=1,m1=1;
for(int x=1;x<=sz2[v]*2;x++){
for(int y=1;y<=sz2[u]*2;y++){
tmp[m][x+y]=min(tmp[m][x+y],dp[m][v][x]+dp[m1][u][y]);
}
}
for(int m=1;m<2;m++){
for(int i=0;i<n*2+10;i++){
dp[m][v][i]=tmp[m][i];
}
}
sz2[v]+=sz2[u];
}
for(int i=0;i<n;i++){
for(int j=n*2-1;j>=0;j--){
dp[3][i][j]=min(dp[3][i][j+1],dp[3][i][j]);
dp[1][i][j]=min(dp[1][i][j+1],dp[1][i][j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<=n*2;j++){
if(dp[3][x][j]<=k){
ans=max(ans,j);
}
}
}
for(int i=0;i<ord.size()-1;i++){
int v=ord[i],u=ord[i+1];
int j=0;
for(int i=n*2;i>=0;i--){
while(j<n*2 && dp[3][u][j+1]+dp[1][v][i]<=k){
j++;
}
if(dp[3][u][j]+dp[1][v][i]<=k){
ans=max(ans,i+j);
}
}
}
return ans;
}
Compilation message
closing.cpp: In function 'void init()':
closing.cpp:27:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
27 | is[i]=sz[i]=0;
| ~~~~~^~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:137:5: error: 'cost' was not declared in this scope; did you mean 'cost2'?
137 | if(cost[y]>2*k){
| ^~~~
| cost2
closing.cpp:178:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int i=0;i<ord.size()-1;i++){
| ~^~~~~~~~~~~~~
closing.cpp:211:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for(int i=0;i<ord.size()-1;i++){
| ~^~~~~~~~~~~~~
