#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int max_score(int N, int X, int Y, long long K,
vector<int> U, vector<int> V, vector<int> W) {
vector <pair<int, int>> adj[N];
for (int i = 0; i < N - 1; i++) {
adj[U[i]].push_back({V[i], W[i]});
adj[V[i]].push_back({U[i], W[i]});
}
vector <ll> D[2];
D[0] = vector<ll>(N);
D[1] = vector<ll>(N);
int XY[2] = {X, Y};
vector<int> x2y;
for (int t: {0, 1}) {
D[t][XY[t]] = 0;
vector<int> P;
function<void(int, int)> dfs = [&](int i, int p) -> void {
P.push_back(i);
if (t == 0 && i == Y) {
x2y = P;
}
for (auto j: adj[i]) {
if (j.first == p) {
continue;
}
D[t][j.first] = D[t][i] + j.second;
dfs(j.first, i);
}
P.pop_back();
};
dfs(XY[t], -1);
}
int m = 0;
while (m + 1 < x2y.size() && d[0][x2y[m + 1]] <= d[1][x2y[m + 1]]) {
m++;
}
int ret = 0;
ll S[2][x2y.size()];
ll s = 0;
for (int i = 0; i <= m; i++) {
s += D[0][x2y[i]];
s = min(s, K + 1);
S[0][i] = s;
}
s = 0;
for (int j = x2y.size() - 1; j > m; j--) {
s += D[1][x2y[j]];
s = min(s, K + 1);
S[1][j] = s;
}
for (int i = 0; i <= m; i++) {
for (int j = x2y.size() - 1; j > m; j--) {
if (S[0][i] + S[1][j] <= K) {
ret = max(ret, i + 1 + (int(x2y.size()) - j));
}
}
}
if (S[0][m] + S[1][m + 1] <= K) {
ll X[2][x2y.size()];
ll s = 0;
X[0][m + 1] = 0;
for (int i = m; i >= 0; i--) {
s += D[1][x2y[i]] - D[0][x2y[i]];
s = min(s, K + 1);
X[0][i] = s;
}
s = 0;
X[1][m] = 0;
for (int j = m + 1; j < x2y.size(); j++) {
s += D[0][x2y[j]] - D[1][x2y[j]];
s = min(s, K + 1);
X[1][j] = s;
}
for (int i = 0; i <= m + 1; i++) {
for (int j = x2y.size() - 1; j >= m; j--) {
if (S[0][m] + S[1][m + 1] + X[0][i] + X[1][j] <= K) {
ret = max(ret, int(x2y.size()) + (m + 1 - i) + (j - m));
}
}
}
}
return ret;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (m + 1 < x2y.size() && d[0][x2y[m + 1]] <= d[1][x2y[m + 1]]) {
| ~~~~~~^~~~~~~~~~~~
closing.cpp:41:34: error: 'd' was not declared in this scope
41 | while (m + 1 < x2y.size() && d[0][x2y[m + 1]] <= d[1][x2y[m + 1]]) {
| ^
closing.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int j = m + 1; j < x2y.size(); j++) {
| ~~^~~~~~~~~~~~
