Balanslaşdırılmış Axın Ağacı#12237

Balanslaşdırılmış Axın Ağacı (Həll təhlili)

Məsələnin müəllifi:	Imran AKKI
Hazırlayan:	Imran AKKI
Redaktə edən:	Hasan Saleh (MathModel)

Həll bir keçidlik yarpaq-soyma qreedy alqoritmi: $rem [u] = b [u]$ \text{rem}[u]=b[u] götürün (hər düyün üçün qalmalı olan çıxış-giriş balansı), bütün yarpaqları növbəyə atın və təkrarlayaraq hər dəfə yarpaq $u$ -nu və onun yeganə istifadə olunmamış qırağını $e = (u, p)$ e=(u,p) silin. Əgər $u$ yalnız o qırağa malikdirsə, onda həmin qıraq $u$ -ya $+ 1$ (əgər $u \to p$ u \rightarrow p) və ya $- 1$ (əgər $p \to u$ p \rightarrow u) qatqı verir; buna görə də $rem [u]$ mütləq $+ 1$ və ya $- 1$ olmalıdır. Qırağı uyğun istiqamətləndirin, istifadə olunmuş kimi işarələyin, $u$ -nu silin (dərəcəni azaldın), və qonşuya ötürülən təsiri belə yeniləyin: $rem [p] = rem [p] + rem [u]$ \text{rem}[p]=\text{rem}[p]+\text{rem}[u].

Əgər hər hansı anda yarpaq $u$ üçün $rem [u] \in / {+ 1, - 1}$ \text{rem}[u] \notin \{+1,-1\} olarsa, NO qaytarın.

Bütün qıraqlar istiqamətləndirildikdə (onda cavab YES) və ya ziddiyyət aşkarlananda dayanın. Bu alqoritm düzgündür, çünki hər hansı qlobal həll istənilən vaxt yarpaq düyünündə eyni məcburi seçimi yaradır (yarpağa bağlı qıraq yalnız $\pm 1$ verə bilər). Ona görə də qreedy yanaşmamız istənilən həlli bərpa edir; əksinə, əgər alqoritm yarpaqda uğursuz olursa, onda qlobal həll mümkün deyil.

Ümumi mürəkkəblik: $O (n)$ .

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

Mürəkkəblik : $O (n)$