Будем решать задачу, если кол-во положительных чисел чётно и кол-во отрицательных чисел чётно (иначе объединим в пару максимальное отрицательное число и минимальное положительное число). Решим для положительных, для отрицательных будет аналогично. Пусть $$$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();
}

Цифровой бор умеет решать следующую задачу за $$$O(log(max(x_i)))$$$: есть множество чисел {$$$x_i$$$}, по заданному числу $$$y$$$ найти максимальное значение $$$y \oplus x_i$$$.

Пусть $$$path(v, u)$$$ — множество значений вершин на пути от $$$v$$$ до $$$u$$$, $$$xr_v$$$ — ксор всех чисел на пути от вершины $$$1$$$ до $$$v$$$. Ксор чисел на пути от $$$v$$$ до $$$u$$$ будет равняться $$$xr_v \oplus xr_u \oplus xr_{lca(v, u)}$$$. Для каждой вершины $$$v$$$ найдем цифорвые боры $$$L$$$, $$$M$$$, и $$$R$$$:

Для каждой вершины $$$u$$$ в поддереве вершины $$$v$$$

1. Если $$$max(path(v, u)) \lt c$$$, то $$$xr_u$$$ добавляется в цифровой бор $$$L$$$.

2. Если $$$min(path(v, u)) \gt c$$$, то $$$xr_u$$$ добавляется в $$$R$$$.

3. Иначе $$$xr_u$$$ добавляется в $$$M$$$.

Поддерживать эти три цифровых бора для каждой вершины можно с помощью метода переливаний. В процессе переливаний будем обновлять ответ. Также нужно не забыть учесть вертикальные пути и пути, состоящие из 1 вершины.

#include <bits/stdc++.h>
#define all(array) array.begin(), array.end()
#define pb push_back
#define eb emplace_back
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using namespace std;
const long long INF = (long long)2e18 + 11;
const int inf = 1e9 + 11;
const int MOD = 998244353;
const int P = 73;


const int LOG = 30;


struct Trie {
    struct Node {
        Node *to[2];

        Node() {
            for (int i = 0; i < 2; ++i) {
                to[i] = nullptr;
            }
        }
    };

    vector<int> vec;
    Node *root = new Node();

    void insert(int x) {
        vec.pb(x);
        Node *v = root;
        for (int i = LOG - 1; i >= 0; --i) {
            int bt = 1 & (x >> i);
            if (!v->to[bt]) {
                v->to[bt] = new Node();
            }
            v = v->to[bt];
        }
    }

    void insert(vector<int> a) {
        for (int x : a) {
            insert(x);
        }
    }

    int get(int x) {
        if (vec.empty()) {
            return -1;
        }
        int ans = 0;
        Node *v = root;
        for (int i = LOG - 1; i >= 0; --i) {
            int bt = 1 & (x >> i);
            if (v->to[1 - bt]) {
                ans |= 1 << i;
                v = v->to[1 - bt];
            } else {
                v = v->to[bt];
            }
        }
        return ans;
    }
};


int c;
int ans = -1;


struct Value {
    Trie l, m, r;

    void upd(int x) {
        if (x <= c) {
            m.insert(r.vec);
            r = Trie();
        }
        if (x >= c) {
            m.insert(l.vec);
            l = Trie();
        }
    }

    void insert(int x, int y) {
        if (x < c) {
            l.insert(y);
        } else if (x == c) {
            m.insert(y);
        } else {
            r.insert(y);
        }
    }

    void merge(Value val, int y) {
        for (int x : val.l.vec) {
            ans = max(ans, max(m.get(x ^ y), r.get(x ^ y)));
        }
        for (int x : val.m.vec) {
            ans = max(ans, max(l.get(x ^ y), max(m.get(x ^ y), r.get(x ^ y))));
        }
        for (int x : val.r.vec) {
            ans = max(ans, max(l.get(x ^ y), m.get(x ^ y)));
        }
        val.upd(y);
        l.insert(val.l.vec);
        m.insert(val.m.vec);
        r.insert(val.r.vec);
    }
};


const int N = 1e5;
vector<int> graph[N];
int a[N];
int sz[N], xr[N];


void dfs0(int v, int p) {
    if (p == -1) {
        xr[v] = a[v];
    } else {
        xr[v] = xr[p] ^ a[v];
    }
    sz[v] = 1;
    for (int u : graph[v]) {
        if (u != p) {
            dfs0(u, v);
            sz[v] += sz[u];
        }
    }
}


Value dfs(int v, int p) {
    int big = -1;
    for (int u : graph[v]) {
        if (u != p) {
            if (big == -1 || sz[u] > sz[big]) {
                big = u;
            }
        }
    }
    if (big == -1) {
        Value val;
        val.insert(a[v], xr[v]);
        if (a[v] == c) {
            ans = max(ans, a[v]);
        }
        return val;
    }
    Value val = dfs(big, v);
    val.upd(a[v]);
    val.insert(a[v], xr[v]);
    for (int u : graph[v]) {
        if (u != p && u != big) {
            Value tmp_val = dfs(u, v);
            val.merge(tmp_val, a[v]);
        }
    }
    ans = max(ans, val.m.get(a[v] ^ xr[v])); // vertical path
    return val;
}


void solve() {
    int n;
    cin >> n >> c;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int x, y;
    for (int i = 0; i < n - 1; ++i) {
        cin >> x >> y;
        --x, --y;
        graph[x].pb(y);
        graph[y].pb(x);
    }
    dfs0(0, -1);
    dfs(0, -1);
    cout << ans;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc = 1;
    int cfmode = 0;
    if (cfmode) {
        cin >> tc;
    }
    while (tc--) {
        solve();
        if (tc) {
            cout << '\n';
        }
    }
    return 0;
}