And again trees (Editorial)

Problem Author:	Andriy Kholod (Connect)
Prepared by:	Andriy Kholod (Connect)
Analysis:	Andriy Kholod (Connect)

Idea

We perform a preorder traversal of the tree: a vertex is recorded in an array at the moment of entering it, and the order of traversing the children can be chosen arbitrarily.

We need to maximize the number of positions where the value is a new record, i.e., strictly greater than everything that has been encountered before.

In other words, during the traversal, we maintain the current maximum. If at the moment of entering a vertex its value is greater than the current maximum, we get $+ 1$ to the answer.

The entire complexity of the problem lies in the fact that subtrees can be rearranged.

1) What is important about the subtree

For each vertex $v$ , we will precompute:

cnt[v] — the size of the subtree;
mx[v] — the maximum value in the subtree.

This is done with a simple DFS.

Why is mx[v] important? Because if the current record is no less than mx[v], then from the entire subtree $v$ we will not get any new prefix maximums.

Thus, the subtree is naturally described by the function: $d p_{v} (x)$ dp_v(x) = the maximum number of new records in subtree $v$ , if before entering it the current maximum is equal to $x$ .

However, we cannot store this function for all $x$ directly.

2) What does the DP function look like

If we increase the starting maximum $x$ , the answer cannot increase. That is, $d p_{v} (x)$ dp_v(x) is monotonic non-decreasing? No, it is actually a non-increasing function.

Moreover, it changes only at points related to values from the tree. Therefore, it can be stored as a set of "breakpoints": $(x, d p_{v} (x))$ (x, dp_v(x)).

In the code, such states are stored in the set cur_have or temporarily in tmp. Moreover, only non-dominated pairs are stored:

if for a greater or equal $x$ the value is not worse, the old state will never be needed;
therefore, it can be removed.

This is exactly what the functions ins_tmp and ins_have do.

3) What does a state in the set mean

The set stores pairs $(x, v a l)$ (x, val),

where $x$ is the minimum required starting maximum, and $v a l$ is the best answer.

The query $g e t_d p_ha v e (v, x)$ get\_dp\_have(v, x) means: if before the subtree the current maximum is equal to $x$ , how many new prefix maximums can we still obtain?

Since the function is stored as a broken line at the breakpoints, it is sufficient to find the first pair with a key not less than $x$ :

The same works for tmp.

4) Why should children be processed in descending order of mx

Before merging, the code sorts the children:

This is a very important structural observation.

If we first traverse the subtree with a smaller maximum element, and then with a larger one, then the large subtree may "consume" part of the potential records of the small one. On the other hand, if we first traverse the subtree with a larger mx, then after it the record will become larger, and this will not harm those subtrees with smaller maximums — they would not have contributed much after such a record anyway.

In such a DP, the optimal order of children turns out to be precisely the order of descending maximums of the subtrees.

This is the reason for sorting.

5) Small-to-large merging

The main idea of the implementation is DSU on tree / small-to-large.

For vertex $v$ , we choose the "heavy" child big — the one with the largest subtree:

Why is this? To avoid copying large structures multiple times. We store the DP of the heavy child as the main container, and all light subtrees are merged into it one by one.

This gives a total complexity of nearly linear-logarithmic.

6) How exactly are subtrees merged

Let the children already be sorted in descending order of mx.

Then, when building the DP for vertex $v$ , there are two stages.

Stage 1. Prepare the contribution of all children that come before big

For light children that stand before big in this order, the values are accumulated in a temporary structure tmp.

The idea is as follows: if we have already traversed several subtrees with larger maximums, then for the next subtree the starting record is no less than its mx[to]. Therefore, the additional contribution of the previous subtrees can be extracted through get_dp_tmp(mx[to]).

Stage 2. Take the DP of the heavy child as the base

After this, the DP of the heavy subtree becomes the basis for the entire vertex:

Here add[v] is a lazy shift for all values in the structure. It means: "to all answers of this container, we need to add this much more." This allows us not to traverse the entire set each time and not to increase all values manually.

7) Why is add[v] needed

When we add to the already prepared DP the contribution of some subtrees, we often just need to increase the entire function by the same constant.

To avoid changing all pairs in the set, the code stores them in a "normalized" form, and the actual value is returned as a value with a constant. And when inserting, it subtracts this shift.

8) What do we do with children after big

After the base is built on the heavy child, the remaining children that stand after it in descending order of mx are added to it.

The logic is the same:

when we add a new subtree, everything that has already been collected earlier affects it only through the current maximum, i.e., through mx[to].

9) How the vertex itself is added

After processing all children, we need to account for vertex $v$ .

If before entering $v$ the current maximum is less than $c [v]$ , then at the vertex itself we get another prefix maximum.

What happens here:

we query the best answer if before entering the maximum is equal to $c [v]$ ;
we add $+ 1$ for the vertex itself;
all states with a key less than $c [v]$ become irrelevant, because after visiting $v$ the maximum can no longer be less than $c [v]$ .

This is the DP transition for the vertex.

10) Why at the end the answer is get_dp_have(root, -1)

After coordinate compression, all values are non-negative. Thus, the starting maximum "before the traversal begins" can be considered equal to $- 1$ .

Then: $d p_{root} (- 1)$ dp_{\text{root}}(-1) is the maximum possible number of prefix maximums in the entire traversal.

13) Asymptotics

DFS for cnt and mx: $O (n)$ .
Sorting the lists of children in total: $O (n lo g n)$ O(n \log n).
Each DP state is transferred between containers a limited number of times due to small-to-large.

Total complexity: $O (n lo g^{2} n)$ O(n \log^2 n) or close to it depending on the details of the operation of set.

Solution Code

//#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;   // current maximum after traversal
    int cnt;  // how many prefix maximums have already been counted
};

// if we need a strictly "new record" -> replace >= with >
static inline bool is_prefix_max(int val, int curMx) {
    return val > curMx;
}

State bruteDfs(int v, int p, int curMx, int curCnt) {
    // visit v (pre-order)
    if (is_prefix_max(c[v], curMx)) curCnt++;
    curMx = max(curMx, c[v]);

    // children (neighbors without the parent)
    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++