A. Line Trip

The fuel tank must be sufficient to cover the distance between every pair of consecutive gas stations, and must also allow returning from the destination back to the start point without refueling at the final station.

Click to view solution code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int n, destination;
        cin >> n >> destination;
        vector<int> station(n + 1);
        station[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> station[i];
        }
        
        int max_gap = 0;
        for (int i = 1; i <= n; i++) {
            max_gap = max(max_gap, station[i] - station[i - 1]);
        }
        max_gap = max(max_gap, (destination - station[n]) * 2);
        cout << max_gap << "\n";
    }
    return 0;
}

B. Chip and Ribbon

For each consecutive pair where a[i-1] < a[i], at least (a[i] - a[i-1]) operations are reqiured to transform a[i-1] into a[i]. The first element does not require any transformation.

Click to view solution code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int len;
        cin >> len;
        vector<long long> arr(len + 1);
        arr[0] = 0;
        for (int i = 1; i <= len; i++) {
            cin >> arr[i];
        }
        
        long long result = 0;
        for (int i = 1; i <= len; i++) {
            result += max(arr[i] - arr[i - 1], 0LL);
        }
        cout << result << "\n";
    }
    return 0;
}

C. Add, Divide and Floor

Refer to the solution on Luogu.

D. Yet Another Monster Fight

Refer to the solution on Luogu.

E. Compressed Tree

This is a tree dynamic programming problem where any node can serve as the root. The goal is to find the maximum sum of node values along any path in the tree.

Click to view sloution code

#include <bits/stdc++.h>
using namespace std;

const long long NEG_INF = -4e18;
const int MAXN = 500005;

int num_vertices;
int weight[MAXN];
vector<int> graph[MAXN];

long long subtree_best[MAXN];
long long global_answer;

void traverse(int current, int parent) {
    vector<long long> child_values;
    subtree_best[current] = weight[current];
    global_answer = max(global_answer, (long long)weight[current]);
    
    for (int neighbor : graph[current]) {
        if (neighbor == parent) continue;
        traverse(neighbor, current);
        child_values.push_back(subtree_best[neighbor]);
        global_answer = max(global_answer, weight[current] + subtree_best[neighbor]);
        subtree_best[current] = max(subtree_best[current], subtree_best[neighbor]);
    }
    
    sort(child_values.begin(), child_values.end(), greater<long long>());
    
    if (child_values.size() > 1) {
        long long combined = child_values[0] + child_values[1];
        global_answer = max(global_answer, combined);
        for (size_t i = 2; i < child_values.size(); i++) {
            if (child_values[i] > 0) {
                combined += child_values[i];
            }
        }
        subtree_best[current] = max(subtree_best[current], weight[current] + combined);
    }
    
    if (child_values.size() > 2) {
        long long combined = child_values[0] + child_values[1] + child_values[2];
        for (size_t i = 3; i < child_values.size(); i++) {
            if (child_values[i] > 0) {
                combined += child_values[i];
            }
        }
        global_answer = max(global_answer, weight[current] + combined);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        cin >> num_vertices;
        for (int i = 1; i <= num_vertices; i++) {
            cin >> weight[i];
        }
        
        for (int i = 0; i < num_vertices - 1; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        global_answer = 0;
        traverse(1, 0);
        cout << global_answer << "\n";
        
        for (int i = 1; i <= num_vertices; i++) {
            graph[i].clear();
        }
    }
    return 0;
}