for x ≥ 40

There is an solution with about 10 lines of essential code.

Let's consider any rooted subtree with k vertices. For every integer x define f(x) as the minimum number of operations required to obtain the tree with vertex values nondecreasing root-to-leaves and the root value at least x. It's obvious that f(x) is nondecreasing itself and f(x) = k when x is large enough. Let's define a multiset "up": for every number x we add x to it f(x + 1) - f(x) times (for example for one vertex subtree that would be just one number equal to the number of this vertex a[v]). The answer for the problem would therefore be n minus the number of elements in up[0]. The only thing left is to do a dfs and for every vertex v get up[v] from up[u] of all its children. Not hard to see that by definition up[v] would be a union of all up[u] from which we erase a maximum number which is less than a[v]. Now if we unite these multisets small to big each time the total complexity would be .

int n;
vector<int> a;
vector<vector<int>> nb;
vector<multiset<int>> up;

void dfs(int v, int p) {
    for(auto u : nb[v]) if(u!=p) {
        dfs(u, v);
        if(up[u].size() > up[v].size()) swap(up[u], up[v]);
        for(auto x : up[u]) up[v].insert(x);
    }
    auto it = up[v].lower_bound(a[v]);
    if (it != up[v].begin()) {
        it--;
        up[v].erase(it);
    }
    up[v].insert(a[v]);
}

int main()
{
    scanf("%d", &n);
    a.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    nb.resize(n);
    up.resize(n);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--, v--;
        nb[u].push_back(v); 
        nb[v].push_back(u);
    }
    dfs(0, 0);
    cout << n-up[0].size();
}

//sorry for my poor English

Solve each a_i independently Now, assume that we are solving a_i = x First, get all the factors of x first. This spend O(sqrt(MAX(a_i))) . Then, we can solve it with dp dp[i] means the best answer for solving a stick which has length i, initially, dp[1] = 1

We can get the transform: dp[i] = max( dp[j]*(i/j) + 1, for all j such that i%j==0 and i!=j )

This spend about O( (factor of x)^2 ) times

for 12=2*2*3;in increasing order ans=6(1+ 1/2+ 1/(2*2)+ 1/(2*2*3))