І знову дерева (Розбір)

//#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;   // поточний максимум після обходу
    int cnt;  // скільки префіксних максимумів вже нараховано
};

// якщо треба строго "новий рекорд" -> заміни >= на >
static inline bool is_prefix_max(int val, int curMx) {
    return val > curMx;
}

State bruteDfs(int v, int p, int curMx, int curCnt) {
    // відвідуємо v (pre-order)
    if (is_prefix_max(c[v], curMx)) curCnt++;
    curMx = max(curMx, c[v]);

    // діти (сусіди без батька)
    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!
*/