Árbol de Flujo Balanceado#12237

Árbol de Flujo Balanceado (Editorial)

Autor del Problema:	Imran AKKI
Preparado por:	Imran AKKI
Editado por:	Hasan Saleh (MathModel)

Solución Un algoritmo codicioso de eliminación de hojas en una sola pasada: mantener $rem [u] = b [u]$ \text{rem}[u]=b[u] (el valor restante out-in que debe cumplirse en cada vértice), poner todas las hojas en una cola y repetidamente quitar cualquier hoja $u$ con su única arista no usada $e = (u, p)$ e=(u,p). Cuando $u$ solo tiene esa arista, la contribución de $e$ a $u$ debe ser $+ 1$ (si $u \to p$ u \rightarrow p) o $- 1$ (si $p \to u$ p \rightarrow u), entonces $rem [u]$ debe ser $+ 1$ o $- 1$ ; orientar la arista $e$ en consecuencia, marcarla como usada, eliminar $u$ (decrementar grados), y propagar el efecto al vecino con $rem [p] = rem [p] + rem [u]$ \text{rem}[p]=\text{rem}[p]+\text{rem}[u].

Si en algún momento una hoja $u$ tiene $rem [u]$ no en ${+ 1, - 1}$ , reporta NO.

Continuar hasta que todas las aristas estén orientadas (entonces YES) o se detecte una contradicción. Esto es correcto porque cualquier orientación global válida induce la misma elección forzada siempre que un vértice se convierta en hoja (una arista a una hoja solo puede dar $\pm 1$ ), por lo que nuestro algoritmo codicioso coincide con cualquier solución y, por inducción en el número de vértices, la reconstruye si existe; de lo contrario, si el algoritmo falla en alguna hoja, ninguna orientación global puede satisfacer el valor requerido restante de esa hoja.

La complejidad total es $O (n)$ .

// Autor: 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++

Complejidad : $O (n)$