Емоції Тето#12449

Емоції Тето (Розбір)

Автор задачі:	Деркач Тарас
Підготував:	Деркач Тарас
Розбір:	Деркач Тарас

Розв'язання

Зафіксуємо вершину $v$ , яку ми обираємо центральною.

Після цього видаляються всі вершини на відстані рівно $2$ від $v$ .

Подивимось, які зв'язані частини залишаться.

Перша частина завжди містить саму вершину $v$ та всіх її сусідів. Позначимо її суму як $ce n t e r_{v}$ center_v:

ce n t e r_{v} = a_{v} + u \in a d j_{v} \sum a_{u} .

center_v = a_v + \sum_{u \in adj_v} a_u.

Інші частини можуть з'явитися тільки за вершинами, які були видалені.

Нехай $u$ — сусід вершини $v$ , а $x$ — сусід вершини $u$ , причому $x \neq = v$ x \ne v.

Тоді вершина $x$ знаходиться на відстані рівно $2$ від $v$ , тому вона видаляється. Після видалення $x$ можуть залишитися частини, які лежать за її іншими сусідами.

Тобто нам потрібно швидко знати таке значення:

якщо є ребро $(x, y)$ , то яка сума компоненти, що лежить з боку вершини $y$ , якщо прибрати це ребро.

Позначимо цю суму як $s i d e (x, y)$ side(x,y).

Якщо укорінити дерево в вершині $1$ , то $s i d e (x, y)$ side(x,y) легко рахується через суми піддерев:

якщо $y$ є сином $x$ , то $s i d e (x, y) = s u b t r e e_{y}$ side(x,y) = subtree_y;
інакше $s i d e (x, y) = t o t a l - s u b t r e e_{x}$ side(x,y) = total - subtree_x.

Для кожної вершини $x$ збережемо два найменші та два найбільші значення серед усіх $s i d e (x, y)$ side(x,y) по сусідах $y$ .

Навіщо два? Бо іноді нам треба взяти найкраще значення, але заборонити один конкретний напрямок. Наприклад, коли ми дивимось на видалену вершину $x$ , не можна брати напрямок назад до $u$ , бо звідти прийшли до $x$ .

Далі для кожної вершини $u$ збережемо найменші та найбільші суми компонент, які можуть з'явитися після видалення одного із сусідів $x$ вершини $u$ .

Іншими словами, для кожного сусіда $x$ вершини $u$ беремо найкращу компоненту за $x$ , але не в напрямку назад до $u$ .

Після такої підготовки відповідь для конкретної центральної вершини $v$ можна знайти швидко.

Спочатку маємо компоненту з сумою $ce n t e r_{v}$ center_v.

Потім для кожного сусіда $u$ вершини $v$ беремо найменшу та найбільшу можливу компоненту за вершинами, які знаходяться за $u$ . При цьому треба заборонити напрямок назад до $v$ .

Серед усіх знайдених компонент знаходимо мінімальну та максимальну суму. Контраст для вершини $v$ дорівнює:

ma x S u m - min S u m .

maxSum - minSum.

Відповідь — максимум цього значення серед усіх вершин $v$ .

Приклад

У першому прикладі оптимально вибрати вершину $v = 4$ v = 4.

Тоді вершина $2$ знаходиться на відстані рівно $2$ від неї, тому вона видаляється.

Після видалення залишаються дві зв'язані частини:

${1}$ із сумою $1$ ;
${3, 4, 5}$ \{3,4,5\} із сумою $3 + 4 + 5 = 12$ 3 + 4 + 5 = 12.

Отже, контраст дорівнює:

12 - 1 = 11.

12 - 1 = 11.

Асимптотика

Ми один раз рахуємо суми піддерев, після цього для кожної вершини переглядаємо її сусідів.

Кожне ребро обробляється лише константну кількість разів.

Тому складність розв'язання становить $O (n)$ .

Розв'язок

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = (1LL << 62);

struct BestMin {
    pair<ll, int> first = {INF, -1};
    pair<ll, int> second = {INF, -1};

    void add(ll value, int id) {
        if (value < first.first) {
            second = first;
            first = {value, id};
        } else if (value < second.first) {
            second = {value, id};
        }
    }

    ll get(int banned_id) {
        if (first.second == banned_id) return second.first;
        return first.first;
    }
};

struct BestMax {
    pair<ll, int> first = {-INF, -1};
    pair<ll, int> second = {-INF, -1};

    void add(ll value, int id) {
        if (value > first.first) {
            second = first;
            first = {value, id};
        } else if (value > second.first) {
            second = {value, id};
        }
    }

    ll get(int banned_id) {
        if (first.second == banned_id) return second.first;
        return first.first;
    }
};

void solve() {
    int n;
    cin >> n;

    vector<ll> a(n + 1);
    ll total = 0;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total += a[i];
    }

    vector<vector<int>> g(n + 1);

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> parent(n + 1, 0);
    vector<int> order;

    order.push_back(1);

    for (int i = 0; i < (int)order.size(); i++) {
        int v = order[i];

        for (int to : g[v]) {
            if (to == parent[v]) continue;

            parent[to] = v;
            order.push_back(to);
        }
    }

    vector<ll> subtree(n + 1);

    for (int i = 1; i <= n; i++) {
        subtree[i] = a[i];
    }

    for (int i = n - 1; i >= 1; i--) {
        int v = order[i];
        subtree[parent[v]] += subtree[v];
    }

    vector<BestMin> edge_min(n + 1);
    vector<BestMax> edge_max(n + 1);

    for (int x = 1; x <= n; x++) {
        for (int y : g[x]) {
            ll side_sum;

            if (parent[y] == x) {
                side_sum = subtree[y];
            } else {
                side_sum = total - subtree[x];
            }

            edge_min[x].add(side_sum, y);
            edge_max[x].add(side_sum, y);
        }
    }

    vector<BestMin> behind_min(n + 1);
    vector<BestMax> behind_max(n + 1);

    for (int u = 1; u <= n; u++) {
        for (int x : g[u]) {
            ll mn = edge_min[x].get(u);
            ll mx = edge_max[x].get(u);

            if (mn != INF) {
                behind_min[u].add(mn, x);
            }

            if (mx != -INF) {
                behind_max[u].add(mx, x);
            }
        }
    }

    ll answer = 0;

    for (int v = 1; v <= n; v++) {
        ll center = a[v];

        for (int u : g[v]) {
            center += a[u];
        }

        ll mn = center;
        ll mx = center;

        for (int u : g[v]) {
            ll cur_min = behind_min[u].get(v);
            ll cur_max = behind_max[u].get(v);

            if (cur_min != INF) {
                mn = min(mn, cur_min);
            }

            if (cur_max != -INF) {
                mx = max(mx, cur_max);
            }
        }

        answer = max(answer, mx - mn);
    }

    cout << answer << endl;
}

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

    solve();

    return 0;
}