Problem A: Tree Value Maximization

Approach

Define subtree_value[i] as the value generated by the subtree rooted at node i: subtree_value[i] = subtree_size[i] + Σ subtree_value[j] for all children j of i. The initial selection of i as root gives subtree_size[i] value, followed by contributions from its subtrees.

Direct computation for each root yields O(n²) complexity. We optimize using root transition dynamic programming.

Let root_value[i] represent the answer when i is root. Consider transitioning from root x to root y in a tree of size n:

root_value[x] = n + Σ subtree_value[v] for all v in x's subtrees
root_value[x] = n + Σ subtree_value[v] for v in x's children (v ≠ y) + subtree_value[y]
root_value[x] = n + Σ subtree_value[v] for v in x's children (v ≠ y) + subtree_size[y] + Σ subtree_value[u] for u in y's children (u ≠ x)
root_value[x] = n + subtree_value[x] + subtree_size[y] + Σ subtree_value[u] for u in y's children (u ≠ x) - (n - subtree_size[y])
root_value[y] = n + subtree_value[x] + Σ subtree_value[u] for u in y's children (u ≠ x)
∴ root_value[x] = root_value[y] + 2 × subtree_size[y] - n
∴ root_value[y] = root_value[x] - 2 × subtree_size[y] + n

The transition equation for root switching. When n=1, root_value[1] = subtree_value[1].

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int node_count;
    cin >> node_count;
    
    vector<vector<int>> graph(node_count + 1);
    for (int i = 1; i < node_count; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    vector<ll> subtree_val(node_count + 1), root_val(node_count + 1), sizes(node_count + 1);
    
    auto compute_subtree = [&](auto&& self, int node, int parent) -> void {
        sizes[node] = 1;
        for (int child : graph[node]) {
            if (child == parent) continue;
            self(self, child, node);
            sizes[node] += sizes[child];
            subtree_val[node] += subtree_val[child];
        }
        subtree_val[node] += sizes[node];
    };
    
    compute_subtree(compute_subtree, 1, 0);
    
    ll max_result = 0;
    max_result = root_val[1] = subtree_val[1];
    
    auto transition_roots = [&](auto&& self, int node, int parent) -> void {
        if (node != 1) {
            root_val[node] = root_val[parent] + node_count - 2 * sizes[node];
            max_result = max(max_result, root_val[node]);
        }
        
        for (int child : graph[node]) {
            if (child == parent) continue;
            self(self, child, node);
        }
    };
    
    transition_roots(transition_roots, 1, 0);
    cout << max_result << '\n';
    
    return 0;
}

Problem B: Number Sequence Transformation

Approach

Classic problem modeling numbers as graph nodes. Create directed edges from x to y if y = x×2 or y = x/3 (when divisible by 3). This forms a DAG where we need the longest path of length n, solved via topological sorting.

Implementation

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<ll> nums(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    
    vector<int> indegree(n + 1);
    vector<vector<int>> adj(n + 1);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (nums[i] * 2 == nums[j]) {
                adj[i].push_back(j);
                indegree[j]++;
            }
            if (nums[i] % 3 == 0 && nums[i] / 3 == nums[j]) {
                adj[i].push_back(j);
                indegree[j]++;
            }
        }
    }
    
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> result;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result.push_back(current);
        for (int neighbor : adj[current]) {
            if (--indegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    
    for (int idx : result)
        cout << nums[idx] << " \n"[idx == result.back()];
    
    return 0;
}

Problem C: Bitwise Value Maximization

Approach

Operation (x & y, x | y) transfers 1-bits between numbers while preserving total count. Since we maximize sum of squares, we should create largest possible numbers. Count 1-bits per position and greedily construct maximum values.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<ll> arr(n + 1);
    vector<int> bit_count(30);
    
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        for (int bit = 0; bit < 20; bit++) {
            if (arr[i] >> bit & 1)
                bit_count[bit]++;
        }
    }
    
    ll total = 0;
    for (int i = 1; i <= n; i++) {
        ll current = 0;
        for (int bit = 0; bit < 20; bit++) {
            if (bit_count[bit] > 0) {
                current |= (1 << bit);
                bit_count[bit]--;
            }
        }
        total += current * current;
    }
    
    cout << total << '\n';
    return 0;
}

Problem D: Position Correction

Approach

When p[i] = i, swap with adjacent element to fix both positions. Scan array and perform swaps when needed.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> perm(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> perm[i];
    
    int swaps = 0;
    for (int i = 1; i <= n; i++) {
        if (perm[i] != i) continue;
        if (i < n) swap(perm[i], perm[i + 1]);
        else swap(perm[i], perm[i - 1]);
        swaps++;
    }
    
    cout << swaps << '\n';
    return 0;
}

Problem E: String Construction Strategy

Approach

Greedy approach: sort strings and place smallest/largest characters alternately. When a's current character > b's current character, switch placement strategy to prevent advantage to opponent.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str_a, str_b;
    cin >> str_a >> str_b;
    
    sort(str_a.begin(), str_a.end());
    sort(str_b.begin(), str_b.end(), greater<char>());
    
    int total_len = str_a.size();
    
    string front_part = "", back_part = "";
    
    while (str_a.size() > (total_len + 1) / 2) str_a.pop_back();
    while (str_b.size() > total_len / 2) str_b.pop_back();
    
    while (total_len--) {
        if (str_a[0] < str_b[0]) {
            front_part += str_a[0];
            str_a.erase(str_a.begin());
        } else {
            back_part += str_a.back();
            str_a.pop_back();
        }
        
        if (total_len) {
            if (str_a[0] < str_b[0]) {
                front_part += str_b[0];
                str_b.erase(str_b.begin());
            } else {
                back_part += str_b.back();
                str_b.pop_back();
            }
            total_len--;
        }
    }
    
    reverse(back_part.begin(), back_part.end());
    cout << front_part + back_part << '\n';
    
    return 0;
}

Problem F: Tree Range Updates

Approach

Process subtree updates using depth-based difference arrays. During DFS, maintain prefix sums on depth differences. Reverse updates during backtracking to prevent interference between subtrees.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<vector<int>> tree(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    int query_count;
    cin >> query_count;
    
    vector<vector<pair<int, int>>> queries(n + 1);
    while (query_count--) {
        int node, depth, value;
        cin >> node >> depth >> value;
        queries[node].emplace_back(depth, value);
    }
    
    vector<ll> depth_diff(n + 1), result(n + 1);
    
    auto dfs_process = [&](auto&& self, int node, int parent, int depth, ll current_sum) -> void {
        for (auto &[d, val] : queries[node]) {
            depth_diff[depth] += val;
            int end_depth = depth + d + 1;
            if (end_depth <= n) {
                depth_diff[end_depth] -= val;
            }
        }
        
        current_sum += depth_diff[depth];
        result[node] = current_sum;
        
        for (int child : tree[node]) {
            if (child == parent) continue;
            self(self, child, node, depth + 1, current_sum);
        }
        
        for (auto &[d, val] : queries[node]) {
            depth_diff[depth] -= val;
            int end_depth = depth + d + 1;
            if (end_depth <= n) {
                depth_diff[end_depth] += val;
            }
        }
    };
    
    dfs_process(dfs_process, 1, 0, 0, 0);
    
    for (int i = 1; i <= n; i++)
        cout << result[i] << " \n"[i == n];
    
    return 0;
}

Problem G: Numerric Sequence Partitioning

Approach

Dynamic programming: dp[i][j] = number of sequences ending with number from j to i. For length L = i-j+1, numbers with length < L are always smaller. Use prefix sums for optimization. For equal lengths, compare using binary search with hashing.

Implementation

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
using ll = long long;
using ull = unsigned long long;

struct StringHash {
    ull base = 13331;
    vector<ull> powers, hashes;
    
    StringHash(string &s) {
        int n = s.size();
        powers.resize(n + 1);
        hashes.resize(n + 1);
        powers[0] = 1;
        hashes[0] = 0;
        for (int i = 1; i < n; i++) {
            powers[i] = powers[i - 1] * base;
            hashes[i] = hashes[i - 1] * base + s[i];
        }
    }
    
    ull get_hash(int l, int r) {
        return hashes[r] - hashes[l - 1] * powers[r - l + 1];
    }
    
    bool equal_segments(int l1, int r1, int l2, int r2) {
        return get_hash(l1, r1) == get_hash(l2, r2);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    s = " " + s;
    StringHash hasher(s);
    
    auto compare_segments = [&](int start1, int start2) -> bool {
        int low = 0, high = n - start2, max_match = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (hasher.equal_segments(start1, start1 + mid - 1, start2, start2 + mid - 1)) {
                low = mid + 1;
                max_match = mid;
            } else {
                high = mid - 1;
            }
        }
        
        if (max_match == n - start2) return false;
        return s[start1 + max_match] < s[start2 + max_match];
    };
    
    const ll MOD = 1e9 + 7;
    vector<vector<ll>> dp(n + 1, vector<ll>(n + 1));
    vector<vector<ll>> prefix(n + 1, vector<ll>(n + 1));
    
    for (int i = 1; i <= n; i++)
        dp[i][1] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (s[j] == '0') continue;
            int min_idx = max(1, j - (i - j));
            dp[i][j] = (dp[i][j] + (prefix[j - 1][j - 1] - prefix[j - 1][min_idx - 1] + MOD) % MOD) % MOD;
            min_idx--;
            if (min_idx >= 1 && compare_segments(min_idx, j)) {
                dp[i][j] = (dp[i][j] + dp[j - 1][min_idx]) % MOD;
            }
        }
        for (int j = 1; j <= i; j++)
            prefix[i][j] = (prefix[i][j - 1] + dp[i][j]) % MOD;
    }
    
    ll answer = 0;
    for (int i = 1; i <= n; i++)
        answer = (answer + dp[n][i]) % MOD;
    
    cout << answer << '\n';
    return 0;
}

Problem H: Array Equalization

Approach

First verify sum mod n = 0. Transfer all values to first element, then redistribute average. Handle remainders by "loaning" from first element to make values divisible by indices, then returning. Total operations ≤ 3(n-1).

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    
    ll total = 0;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        total += arr[i];
    }
    
    if (total % n != 0) {
        cout << -1 << '\n';
        return;
    }
    
    int target = total / n;
    vector<array<int, 3>> operations;
    
    for (int i = 2; i <= n; i++) {
        if (arr[i] % i != 0) {
            int needed = i - arr[i] % i;
            arr[1] -= needed;
            arr[i] += needed;
            operations.push_back({1, i, needed});
        }
        int transfers = arr[i] / i;
        arr[1] += arr[i];
        arr[i] = 0;
        operations.push_back({i, 1, transfers});
    }
    
    for (int i = 2; i <= n; i++) {
        operations.push_back({1, i, target - arr[i]});
    }
    
    cout << operations.size() << '\n';
    for (auto [from, to, amount] : operations) {
        cout << from << ' ' << to << ' ' << amount << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve();
    }
    
    return 0;
}