#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 3001;
const int off = 1 << logo;
const int trsz = off << 1;
vii g[MAXN];
ll dx[MAXN][2], dp[MAXN][2 * MAXN];
vll vec;
void dfs(int u, int f, int p = -1){
for(auto &y : g[u]){
int x = y.X, w = y.Y;
if(x == p) continue;
dx[x][f] = dx[u][f] + (ll)w;
dfs(x, f, u);
}
}
int max_score(int n, int x, int y, ll k, vi u, vi v, vi w){
for(int i=0; i<n; i++) g[i].clear();
for(int i=0; i<n-1; i++){
g[u[i]].PB({v[i], w[i]});
g[v[i]].PB({u[i], w[i]});
}
dx[x][0] = 0;
dfs(x, 0);
dx[y][1] = 0;
dfs(y, 1);
vec.clear();
int ret = 0;
for(int i=0; i<n; i++){
vec.PB(dx[i][0]);
vec.PB(dx[i][1]);
if(dx[i][0] > dx[i][1]) swap(dx[i][0], dx[i][1]);
}
sort(all(vec));
ll csu = 0;
for(int i=0; i<(int)vec.size(); i++){
csu += vec[i];
if(csu <= k) ret = i + 1;
else break;
}
if(n > 3000) return ret;
for(int i=0; i<=n; i++) for(int j=0; j<=2*i; j++) dp[i][j] = INF;
dp[0][0] = 0;
for(int i=0; i<n; i++){
for(int j=0; j<=2*i; j++){
if(dp[i][j] > k) continue;
if(dx[i][0] + dx[i][1] != dx[x][1]) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + dx[i][0]);
dp[i + 1][j + 2] = min(dp[i + 1][j + 2], dp[i][j] + dx[i][1]);
}
}
for(int j=0; j<=2*n; j++) if(dp[n][j] <= k) ret = max(ret, j);
return ret;
}
Compilation message
/usr/bin/ld: /tmp/ccDgzXD1.o: in function `main':
stub.cpp:(.text.startup+0x95): undefined reference to `longest_trip(int, int)'
collect2: error: ld returned 1 exit status
