Будем решать задачу, если кол-во положительных чисел чётно и кол-во отрицательных чисел чётно (иначе объединим в пару максимальное отрицательное число и минимальное положительное число). Решим для положительных, для отрицательных будет аналогично. Пусть $$$pos$$$ — отсортированный по возрастанию массив положительных чисел. Тогда будем брать в пары числа $$$pos_{2 \cdot i - 1}$$$ и $$$pos_{2 \cdot i}$$$ для $$$i = 1...\frac{n}{2}$$$. Почему нам выгодно брать именно так?

Пусть у нас есть числа $$$a \le b \le c \le d$$$, нужно доказать, что

1. $$$a \cdot b + c \cdot d \ge a \cdot c + b \cdot d$$$

2. $$$a \cdot b + c \cdot d \ge a \cdot d + b \cdot c$$$

Заметим, что для решения нам достаточно было отсортировать по возрастанию массив $$$a$$$ и брать в пары числа $$$a_{2 \cdot i - 1}$$$ и $$$a_{2 \cdot i}.$$$

#include <bits/stdc++.h>
#define all(array) array.begin(), array.end()
using ll = long long;
using namespace std;


void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(all(a));
    ll ans = 0;
    for (ll i = 0; i < n; i += 2) {
        ans += a[i] * a[i + 1];
    }
    cout << ans;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Заметим, что если перевернуть рёбра, то получится корневое дерево с корнем 1. Нужно просто посчитать глубину каждой вершины и взять самую глубокую.

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


void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        graph[y].pb(x);
    }
    vector<int> d(n);
    auto dfs = [&](auto &dfs, int v) -> void {
        for (int u : graph[v]) {
            d[u] = d[v] + 1;
            dfs(dfs, u);
        }
    };
    dfs(dfs, 0);
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        if (d[i] > d[ans] || (d[i] == d[ans] && i < ans)) {
            ans = i;
        }
    }
    cout << ans + 1;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

Пусть $$$to_l$$$ — это максимальное $$$r$$$ $$$(l \le r \le n)$$$, такое, что $$$\gcd\limits_{i=l...r} a_i \gt 1$$$. Посчитаем массив $$$to$$$ двумя указателями: будем перебирать $$$l$$$ от $$$n$$$ до $$$1$$$ и двигать правую границу, когда надо. Для операции $$$gcd$$$ на отрезке построим SparseTable.

Очевидно, что чтобы покрыть отрезок $$$[l_i, r_i]$$$ мы будем использовать отрезки $$$[l_i, to_{l_i}]$$$, $$$[to_{l_i}+1, to_{to_{l_i}+1}]$$$, ... Чтобы быстро определить кол-во отрезков в покрытии посчитаем бинапы на этих отрезочках.

$$$go_{0, i} = to_i+1$$$ $$$(1 \le i \le n)$$$

$$$go_{j, i} = go_{j-1, go_{j-1, i}}$$$ $$$(1 \le i \le n, 1 \le j \le \lceil log_{2}n \rceil)$$$

Как считать ответ — тривиально.

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


const int N = 1e5, LOG = 20;
int sp[LOG][N];


void build(vector<int> a) {
    int n = (int)a.size();
    for (int i = 0; i < n; ++i) {
        sp[0][i] = a[i];
    }
    for (int i = 1; i < LOG; ++i) {
        for (int j = 0; j + (1 << i) <= n; ++j) {
            sp[i][j] = gcd(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
}


int get(int l, int r) {
    int lg = 31 - __builtin_clz(r - l);
    return gcd(sp[lg][l], sp[lg][r - (1 << lg)]);
}


int go[LOG][N + 1];


void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build(a);
    for (int i = 0; i < LOG; ++i) {
        go[i][n] = n;
    }
    int R = n;
    for (int i = n - 1; i >= 0; --i) {
        while (get(i, R) == 1) {
            --R;
        }
        go[0][i] = R;
    }
    for (int i = 1; i < LOG; ++i) {
        for (int j = n - 1; j >= 0; --j) {
            go[i][j] = go[i - 1][go[i - 1][j]];
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int ans = 0;
        for (int i = LOG - 1; i >= 0; --i) {
            if (go[i][l] < r) {
                ans |= 1 << i;
                l = go[i][l];
            }
        }
        ++ans;
        cout << ans << '\n';
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

~~~~~

~~~~~