Збалансоване Дерево Потоку#12237

Збалансоване Дерево Потоку (Розбір)

Автор задачі:	Imran AKKI
Підготував:	Imran AKKI
Редагував:	Hasan Saleh (MathModel)

Розв'язок жадібний алгоритм "здирання листків" за один прохід: зберігаємо $rem [u] = b [u]$ \text{rem}[u]=b[u] (залишкове значення out-in для кожної вершини), кладемо всі листки в чергу та послідовно видаляємо будь-який лист $u$ з його єдиним невикористаним ребром $e = (u, p)$ e=(u,p). Коли у $u$ залишається лише одне ребро, внесок $e$ для $u$ має бути $+ 1$ (якщо $u \to p$ u \rightarrow p) або $- 1$ (якщо $p \to u$ p \rightarrow u), тому $rem [u]$ має дорівнювати $+ 1$ або $- 1$ ; орієнтуємо $e$ відповідно, позначаємо його використаним, видаляємо $u$ (зменшуємо степінь), і додаємо ефект до сусіда: $rem [p] = rem [p] + rem [u]$ \text{rem}[p]=\text{rem}[p]+\text{rem}[u].

Якщо в якийсь момент лист $u$ має $rem [u] \in / {+ 1, - 1}$ \text{rem}[u] \notin \{+1,-1\}, виводимо NO.

Продовжуємо, доки всі ребра не будуть орієнтовані (тоді YES), або не знайдеться суперечність. Це правильно, бо будь-яка правильна глобальна орієнтація зумовлює той самий вибір, коли вершина стає листком (ребро до листка може дати лише $\pm 1$ ), отже наш жадібний алгоритм повторює будь-яке рішення та за індукцією відновлює його, якщо воно існує; навпаки, якщо алгоритм зазнає невдачі на якомусь листку, жодна глобальна орієнтація не може задовольнити вимогу для цього листка.

Загальна складність: $O (n)$ .

// Автор: Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n; cin >> n;
    vector<ll> b(n);
    for(auto &e:b) cin >> e;

    vector<vector<ll>> adj(n);
    for(ll i = 0; i < n - 1; i++) {
        ll u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<ll> deg(n, 0);
    queue<ll> q;
    for(ll i = 0; i < n; i++) {
        deg[i] = adj[i].size();
        if(deg[i] == 1) q.push(i);
    }

    vector<pair<ll, ll>> ans;
    vector<bool> vis(n, 0);
    while(!q.empty()) {
        ll u = q.front(); q.pop();
        if(vis[u] || deg[u] != 1) continue;

        if(b[u] != 1 && b[u] != -1) {
            cout << "NO\n";
            return;
        }

        ll p = -1;
        for(auto v: adj[u]) {
            if(!vis[v]){
                p = v;
                break;
            }
        }

        bool u_to_p = (b[u] == 1);
        if(u_to_p){
            ans.push_back({u, p});
            b[p]++;
        }else{
            ans.push_back({p, u});
            b[p]--;
        }

        vis[u] = 1;
        deg[p]--;
        if(deg[p] == 1) {
            q.push(p);
        }
        deg[u] = 0;
    }
    if((ll)ans.size() != n - 1) {
        cout << "NO\n";
    }else{
        cout << "YES\n";
        for(auto &e: ans) cout << e.first + 1 << " " << e.second + 1 << "\n";
    }
}

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

C++

Складність : $O (n)$