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