Yenə ağaclar#12372
Daxil ol

Yenə ağaclar (Həll təhlili)

Problem Müəllifi:

Andriy Kholod (Connect)

Hazırlayan:

Andriy Kholod (Connect)

Analiz:

Andriy Kholod (Connect)

Fikir

Biz ağacın əvvəlcədən gəzintisini həyata keçiririk: bir zirvə ona daxil olarkən bir massivdə qeyd olunur və uşaqları gəzərkən ardıcıllığı istənilən şəkildə seçmək olar.

Bizə yeni rekord olan dəyərlərin sayını maksimuma çatdırmaq lazımdır, yəni, əvvəllər rast gəlinən hər şeydən daha böyük.

Başqa sözlə, gəzinti zamanı cari maksimumu saxlayırıq. Əgər bir zirvəyə daxil olarkən onun dəyəri cari maksimumdan böyükdürsə, cavaba əlavə edirik.

Problemin bütün çətinliyi, alt ağacların yenidən düzülə bilməsindədir.

1) Alt ağac haqqında nə vacibdir

Hər bir zirvə üçün əvvəlcədən hesablayacağıq:

  • cnt[v] — alt ağacın ölçüsü;

  • mx[v] — alt ağacdakı maksimum dəyər.

Bu, sadə DFS ilə edilir.

Niyə mx[v] vacibdir? Çünki əgər cari rekord mx[v]-dən az deyilsə, onda alt ağacından yeni prefiks maksimumları əldə edə bilməyəcəyik.

Beləliklə, alt ağac funksiyası ilə təbii şəkildə təsvir olunur: dp_v(x) = alt ağac -də yeni rekordların maksimum sayı, əgər ona daxil olmadan əvvəl cari maksimum -ə bərabərdirsə.

Amma bu funksiyanı birbaşa bütün üçün saxlaya bilmirik.

2) DP funksiyası necə görünür

Əgər başlanğıc maksimumu -i artırsaq, cavab artmamalıdır. Yəni, dp_v(x) monoton artan deyil? Xeyr, əslində bu monoton azalan bir funksiyadır.

Bundan əlavə, yalnız ağacdakı dəyərlərlə əlaqəli nöqtələrdə dəyişir. Buna görə də, "qırılma nöqtələri" dəsti kimi saxlanıla bilər: (x, dp_v(x)).

Kodda belə vəziyyətlər cur_have dəstində və ya müvəqqəti olaraq tmp içində saxlanılır. Bundan əlavə, yalnız dominant olmayan cütlər saxlanılır:

  • əgər daha böyük və ya bərabər üçün dəyər daha pis deyilsə, köhnə vəziyyətə ehtiyac olmayacaq;

  • buna görə də, onu silmək olar.

Bu, ins_tmp və ins_have funksiyalarının etdiyi şeydir.

3) Dəstdəki vəziyyət nə deməkdir

Dəst cütləri saxlayır (x, val),

burada tələb olunan minimum başlanğıc maksimumdur, və ən yaxşı cavabdır.

Sorğu get\_dp\_have(v, x) deməkdir: əgər alt ağacdan əvvəl cari maksimum -ə bərabərdirsə, neçə yeni prefiks maksimumu hələ əldə edə bilərik?

Funksiya qırılma xətisi kimi saxlandığı üçün, -dən az olmayan ilk cütü tapmaq kifayətdir:

Eyni şey tmp üçün də işləyir.

4) Niyə uşaqları mx azalan sırası ilə emal etmək lazımdır

Birləşdirmədən əvvəl kod uşaqları sıralayır:

Bu, çox vacib struktural müşahidədir.

Əgər əvvəlcə daha kiçik maksimum elementə malik alt ağacı gəzsək, sonra daha böyük olanı, o zaman böyük alt ağac kiçik olanın potensial rekordlarının bir hissəsini "istehlak" edə bilər. Digər tərəfdən, əgər əvvəlcə daha böyük mx olan alt ağacı gəzsək, o zaman ondan sonra rekord daha böyük olacaq və bu, daha kiçik maksimumlara malik alt ağaclara zərər verməyəcək — belə bir rekorddan sonra onlar da çox şey qatmayacaqdılar.

Belə bir DP-də, uşaqların optimal sırası alt ağacların azalan maksimumlarının sırası olur.

Bu, sıralamanın səbəbidir.

5) Kiçikdən böyüyə birləşdirmə

İcraatın əsas ideyası ağacda DSU / kiçikdən böyüyədir.

Zirvə üçün "ağır" uşağı big seçirik — ən böyük alt ağaca malik olan:

Niyə bu? Böyük strukturları dəfələrlə kopyalamaqdan qaçmaq üçün. Ağır uşağın DP-sini əsas konteyner kimi saxlayırıq və bütün yüngül alt ağacları bir-birinə birləşdiririk.

Bu, ümumi mürəkkəbliyi demək olar ki, xətti-logaritmik edir.

6) Alt ağaclar necə birləşdirilir

Uşaqlar artıq mx azalan sırası ilə sıralanmış olsun.

Sonra, zirvə üçün DP qurarkən iki mərhələ var.

Mərhələ 1. Böyükdən əvvəl gələn bütün uşaqların töhfəsini hazırlayın

Bu sırada big -dən əvvəl duran yüngül uşaqlar üçün dəyərlər müvəqqəti struktur tmp içində toplanır.

Fikir belədir: əgər artıq daha böyük maksimumlara malik bir neçə alt ağacı gəzmişiksə, onda növbəti alt ağac üçün başlanğıc rekord onun mx[to]-dən az olmamalıdır. Buna görə də, əvvəlki alt ağacların əlavə töhfəsini get_dp_tmp(mx[to]) vasitəsilə əldə edə bilərik.

Mərhələ 2. Ağır uşağın DP-sini baza kimi götürün

Bundan sonra, ağır alt ağacın DP-si bütün zirvə üçün əsas olur:

Burada add[v] strukturdakı bütün dəyərlər üçün tənbəl bir köçürmədir. Bu, deməkdir: "bu konteynerin bütün cavablarına bu qədər daha əlavə etməliyik." Bu, hər dəfə bütün dəsti gəzib bütün dəyərləri əl ilə artırmadan etməyə imkan verir.

7) Niyə add[v] lazımdır

Artıq hazırlanmış DP-yə bəzi alt ağacların töhfəsini əlavə edərkən, tez-tez bütün funksiyanı eyni sabitlə artırmaq lazım olur.

Dəstdəki bütün cütləri dəyişdirməkdən qaçmaq üçün, kod onları "normalizə" olunmuş formada saxlayır və faktiki dəyəri sabitlə birlikdə dəyər kimi qaytarır. Və daxil edərkən, bu köçürməni çıxarır.

8) bigdən sonra uşaqlarla nə edirik

Ağır uşaq üzərində baza qurulduqdan sonra, ondan sonra mx azalan sırası ilə duran qalan uşaqlar ona əlavə olunur.

Məntiq eynidir:

növbəti alt ağacı əlavə edərkən, artıq əvvəlcə toplanmış hər şey yalnız cari maksimum vasitəsilə, yəni mx[to] vasitəsilə təsir edir.

9) Zirvənin özü necə əlavə olunur

Bütün uşaqları emal etdikdən sonra, zirvə -ni nəzərə almalıyıq.

Əgər -yə daxil olmadan əvvəl cari maksimum -dən kiçikdirsə, o zaman zirvənin özündə bir prefiks maksimumu daha əldə edirik.

Burada nə baş verir:

  • maksimum -ə bərabərdirsə, ən yaxşı cavabı soruşuruq;

  • zirvənin özü üçün əlavə edirik;

  • -dən kiçik olan bütün vəziyyətlər əhəmiyyətsiz olur, çünki -ni ziyarət etdikdən sonra maksimum artıq -dən kiçik ola bilməz.

Bu, zirvə üçün DP keçididir.

10) Niyə sonunda cavab get_dp_have(root, -1)-dir

Koordinat sıxılmasından sonra, bütün dəyərlər qeyri-mənfidır. Beləliklə, "gəzinti başlamazdan əvvəl" başlanğıc maksimumu -ə bərabər hesab edilə bilər.

Sonra: dp_{\text{root}}(-1) bütün gəzinti boyunca mümkün olan maksimum prefiks maksimumlarının sayıdır.

13) Asimptotiklər

  • cnt və mx üçün DFS: .

  • Uşaqların siyahılarının sıralanması: O(n \log n).

  • Hər DP vəziyyəti kiçikdən böyüyə səbəbindən konteynerlər arasında məhdud sayda ötürülür.

Ümumi mürəkkəblik: O(n \log^2 n) və ya set əməliyyatlarının detallarına görə ona yaxın.

Həll Kodu

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<class T>
using vec = vector<T>;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KoRoVa
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 2e5 + 11, inf = 1000111222;

vector <int> edge[max_n];

int c[max_n], cnt[max_n], mx[max_n];

void dfs (int v, int p = -1) {
    cnt[v] = 1;
    mx[v] = c[v];
    for (int to : edge[v]) {
        if (to == p) {
            continue;
        }
        dfs(to, v);
        cnt[v] += cnt[to];
        umax(mx[v], mx[to]);
    }
}

int add[max_n];

template <int lev, int n>
struct node {

};

template<int n>
struct fast_set {
    int val[max_n];
    // todo
};

set <pii> cur_have, tmp;

inline int get_dp_tmp (int x) {
    auto it = tmp.lower_bound({x, inf});
    if (it == tmp.end()) {
        return 0;
    }
    return it->second;
}

inline void ins_tmp(int x, int val) {
    auto res = tmp.insert({x, val});
    if (!res.second) {
        return;
    }
    auto it = res.first;
    if (next(it) != tmp.end() && next(it)->second >= val) {
        tmp.erase(it);
        return;
    }
    while (it != tmp.begin() && prev(it)->second <= val) {
        tmp.erase(prev(it));
    }
}

inline int get_dp_have (int v, int x) {
    auto it = cur_have.lower_bound({x, inf});
    if (it == cur_have.end()) {
        return 0;
    }
    return it->second + add[v];
}

inline void ins_have(int v, int x, int val) {
    val -= add[v];
    auto res = cur_have.insert({x, val});
    if (!res.second) {
        return;
    }
    auto it = res.first;
    if (next(it) != cur_have.end() && next(it)->second >= val) {
        cur_have.erase(it);
        return;
    }
    while (it != cur_have.begin() && prev(it)->second <= val) {
        cur_have.erase(prev(it));
    }
}

vector <pii> save_val[max_n];

void solve (int v, int p = -1, int save = 0) {
    sort(all(edge[v]), [&] (int a, int b) {
        return mx[a] > mx[b];
    });
    int big = -1;
    for (int to : edge[v]) {
        if (to == p) {
            continue;
        }
        if (big == -1 || cnt[to] > cnt[big]) {
            big = to;
        }
    }
    for (int to : edge[v]) {
        if (to == p || to == big) {
            continue;
        }
        solve(to, v, 0);
    }
    if (big != -1) {
        solve(big, v, 1);
    }

    for (int to : edge[v]) {
        if (to == p) {
            continue;
        }

        int val = get_dp_tmp(mx[to]);
        for (auto &i : save_val[to]) {
            ins_tmp(i.first, i.second + val);
        }

        if (to == big) {
            break;
        }
    }

    if (big != -1) {
        int val = get_dp_tmp(mx[big]);
        swap(add[v], add[big]);
        add[v] += val;
        for (auto &i : tmp) {
            ins_have(v, i.first, i.second);
        }
        tmp.clear();
    }

    bool ok = false;
    for (int to : edge[v]) {
        if (to == p) {
            continue;
        }
        if (ok) {
            int val = get_dp_have(v, mx[to]);
            for (auto &i : save_val[to]) {
                ins_have(v, i.first, i.second + val);
            }
        }
        if (to == big) {
            ok = true;
        }
    }

    int val = get_dp_have(v, c[v]);
    while (!cur_have.empty() && cur_have.begin()->first < c[v]) {
        cur_have.erase(cur_have.begin());
    }
    ins_have(v, c[v], val + 1);

    if (!save) {
        for (auto &i : cur_have) {
            save_val[v].pb({i.first, i.second + add[v]});
        }
        cur_have.clear();
    }
}

int n;
int calc_easy (int root) {
    for (int i = 0; i < n; i++) {
        add[i] = 0;
        cnt[i] = 0;
        mx[i] = 0;
        save_val[i].clear();
    }
    cur_have.clear();
    tmp.clear();
    dfs(root);
//    easy(root);
    solve(root, -1, 1);
    int res = get_dp_have(root, -1);
    return res;
}

struct State {
    int mx;   // gəzinti sonrası cari maksimum
    int cnt;  // artıq neçə prefiks maksimumu sayılıb
};

// əgər sərt "yeni rekord" lazımdırsa -> >= ilə > əvəz edin
static inline bool is_prefix_max(int val, int curMx) {
    return val > curMx;
}

State bruteDfs(int v, int p, int curMx, int curCnt) {
    // v-ni ziyarət et (əvvəlcədən)
    if (is_prefix_max(c[v], curMx)) curCnt++;
    curMx = max(curMx, c[v]);

    // uşaqlar (valideyn olmadan qonşular)
    vector<int> ch;
    for (int to : edge[v]) if (to != p) ch.push_back(to);

    int k = (int)ch.size();
    vector<char> used(k, 0);

    State best{curMx, -1};

    function<void(int,int,int)> go = [&](int done, int mx, int cnt) {
        if (done == k) {
            if (cnt > best.cnt) best = {mx, cnt};
            return;
        }
        for (int i = 0; i < k; i++) if (!used[i]) {
                used[i] = 1;
                State after = bruteDfs(ch[i], v, mx, cnt);
                go(done + 1, after.mx, after.cnt);
                used[i] = 0;
            }
    };

    go(0, curMx, curCnt);
    return best;
}

int brute(int root) {
    State res = bruteDfs(root, -1, INT_MIN, 0);
    return res.cnt;
}

const int debug = 0;

mt19937 rng(228);
template<typename T = int>
inline T randll(T l = INT_MIN, T r = INT_MAX) {
    return uniform_int_distribution<T>(l, r)(rng);
}

inline ld randld(ld l = INT_MIN, ld r = INT_MAX) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    m1:
    for (int i = 0; i < n; i++) {
        edge[i].clear();
    }
    if (!debug) {
        cin >> n;
    }
    else {
        n = randll(2, 20);
    }
    for (int i = 0; i < n; i++) {
        if (!debug) {
            cin >> c[i];
        }
    }
    if (debug) {
        for (int i = 0; i < n; i++) {
            c[i] = randll(0, n);
        }
//        shuffle(c, c + n, rng);
    }
    vector <int> val(n);
    for (int i = 0; i < n; i++) {
        val[i] = c[i];
    }
    sort(all(val));
    val.erase(unique(all(val)), val.end());
    for (int i = 0; i < n; i++) {
        c[i] = lower_bound(all(val), c[i]) - val.begin();
    }
    for (int i = 1, a, b; i < n; i++) {
        if (!debug) {
            cin >> a >> b;
            --a, --b;
        }
        else {
            a = i;
            b = randll(0, i - 1);
        }
        edge[a].pb(b);
        edge[b].pb(a);
    }
    int root = 0;
    int ans = calc_easy(root);
    cout << ans << '\n';
//    LOG(n);
    if (debug) {
        int res = brute(root);
        if (ans != res) {
            exit(4);
        }
        goto m1;
    }
}

/*
KoRoVa!
*/
C++