/* Ignut
started: 13.08.2024
now: 13.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 123;
vector<pair<int, int>> tree[MAXN];
vector<int> order;
int pos[MAXN];
void dfs(int v, int par) {
order.push_back(v);
for (auto [to, w] : tree[v])
if (to != par)
dfs(to, v);
}
ll dx[MAXN], dy[MAXN];
void dfs2(int v, int par, ll d, bool f) {
if (f) dx[v] = d;
else dy[v] = d;
for (auto [to, w] : tree[v])
if (to != par)
dfs2(to, v, d + w, f);
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W) {
order.clear();
for (int i = 0; i < N; i ++)
tree[i].clear();
for (int i = 0; i < N - 1; i ++) {
tree[U[i]].push_back({V[i], W[i]});
tree[V[i]].push_back({U[i], W[i]});
}
dfs2(X, -1, 0, true);
dfs2(Y, -1, 0, false);
int res = 0;
for (int mask = 0; mask < 1 << N; mask ++) {
ll sum = 0;
int ans = 0;
vector<ll> ds;
for (int i = 0; i < N; i ++) {
if (mask & (1 << i)) {
sum += max(dx[i], dy[i]);
ans += 2;
}
else {
ds.push_back(dx[i]), ds.push_back(dy[i]);
}
}
sort(ds.begin(), ds.end());
for (int i = 0; i < ds.size(); i ++) {
if (sum + ds[i] <= K) {
sum += ds[i];
ans ++;
}
}
if (sum <= K) res = max(res, ans);
}
return res;
// ================================================== //
int start = 0;
for (int i = 0; i < N; i ++) {
if (tree[i].size() == 1) {
start = i; break;
}
}
dfs(start, -1);
for (int i = 0; i < N; i ++) pos[order[i]] = i;
if (pos[X] > pos[Y]) {
swap(X, Y);
for (int i = 0; i < N; i ++) swap(dx[i], dy[i]);
}
int res = 0;
for (int l = 0; l < N; l ++) {
for (int r = l; r < N; r ++) {
ll sum = 0;
int ans = (r - l + 1) * 2;
for (int i = l; i <= r; i ++) sum += max(dx[order[i]], dy[order[i]]);
for (int i = pos[X]; i < l; i ++) sum += dx[order[i]], ans ++;
for (int i = pos[Y]; i > r; i --) sum += dy[order[i]], ans ++;
vector<ll> ds;
for (int i = 0; i < min(pos[X], l); i ++) ds.push_back(dx[order[i]]);
for (int i = max(pos[Y], r) + 1; i < N; i ++) ds.push_back(dy[order[i]]);
sort(ds.begin(), ds.end());
for (int i = 0; i < ds.size(); i ++) {
if (sum + ds[i] <= K) {
sum += ds[i];
ans ++;
}
}
if (sum <= K)
res = max(res, ans);
}
}
// no overlap
vector<ll> ds;
for (int i = 0; i < N; i ++) {
ds.push_back(dx[i]);
ds.push_back(dy[i]);
}
sort(ds.begin(), ds.end());
ll sum = 0;
int ans = 0;
for (int i = 0; i < ds.size(); i ++) {
if (sum + ds[i] <= K) {
sum += ds[i];
ans ++;
}
}
res = max(res, ans);
return res;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:83:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 0; i < ds.size(); i ++) {
| ~~^~~~~~~~~~~
closing.cpp:111:9: error: redeclaration of 'int res'
111 | int res = 0;
| ^~~
closing.cpp:68:9: note: 'int res' previously declared here
68 | int res = 0;
| ^~~
closing.cpp:124:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < ds.size(); i ++) {
| ~~^~~~~~~~~~~
closing.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
144 | for (int i = 0; i < ds.size(); i ++) {
| ~~^~~~~~~~~~~
