Language: C++

#include <stdio.h>
#include <algorithm>
#include <utility>

template <const unsigned int N>
struct FastInput{
    char Input[N];
    char* input;
    FastInput(void):Input(), input(Input){ fread_unlocked(Input, sizeof(char), N, stdin); }
    inline int getint(void){
        int res = 0, c; while((c = *(input++) - '0') >= 0) res = 10 * res + c;
        return res;
    }
};

constexpr unsigned int MAX_INPUT = 7400'000;
FastInput<MAX_INPUT> Input;

template <const unsigned int N>
struct FastOutput{
    char Output[N];
    char S[10];
    char* ptr;
    FastOutput(void):Output(), ptr(Output){}
    ~FastOutput(void){ fwrite_unlocked(Output, sizeof(char), ptr - Output, stdout); }
    inline void write(int x){
        if(!x) *(ptr++) = '0';
        else{
            char* p = S;
            while(x){ *p++ = '0' + (x % 10); x /= 10; }
            while(p != S) *ptr++ = *(--p); 
        }
        *(ptr++) = '\n';
    }
};
constexpr unsigned int MAX_OUTPUT = 2400'100;
FastOutput<MAX_OUTPUT> Output;

constexpr unsigned int MAX_N = 100'000;
int A[MAX_N];
int Lis[MAX_N + 1];

struct edge{
    int to; 
    edge* next;
};

edge Edge[2 * MAX_N + 1];
edge* begin[MAX_N];
edge* e_ptr = Edge;
inline void append(const int u, const int v){
    e_ptr -> to = v;
    e_ptr -> next = begin[u];
    begin[u] = e_ptr++;
}

int Ans[MAX_N];
bool visited[MAX_N];

struct stack_type{
    int vertex;
    int val;
};
stack_type Stack[2 * MAX_N + 1];
stack_type * stack = Stack;
inline stack_type* pop(void){ return --stack; }
inline void push(const int v, const int value){ stack -> vertex = v, stack -> val = value; ++stack;}
inline bool empty(void){ return stack == Stack; }

struct Index{
    int index;
    int val;
};
Index Restore[MAX_N];

int main(void){
    int n = Input.getint();
    for(int i = 0; i < n; ++i) A[i] = Input.getint();
    Lis[0] = 0; std::memset(Lis + 1, 0x7f, sizeof(Lis + 1));
    for(int i = 1; i < n; ++i){
        int u = Input.getint() - 1, v = Input.getint() - 1;
        append(u, v); append(v, u);
    }
    visited[0] = true; push(0, 0);
    while(!empty()){
        const stack_type* p = pop();
        const int v = p ->vertex, value = p -> val;
        if(value == -1){ Lis[Restore[v].index] = Restore[v].val; }
        else{
            if(Lis[value] < A[v]){
                Restore[v].index = value + 1; Restore[v].val = INT32_MAX;
                Lis[value + 1] = A[v]; Ans[v] = value + 1;
            }
            else{
                int ok = 0, ng = value;
                while(ng - ok > 1){
                    const int mid = (ok + ng) >> 1;
                    if(Lis[mid] < A[v]) ok = mid; else ng = mid;
                }
                Restore[v].index = ng; Restore[v].val = Lis[ng];
                Lis[ng] = A[v]; Ans[v] = value;
            }
            push(v, -1);
            for(edge* itr = begin[v]; itr; itr = itr -> next) if(!visited[itr -> to]){ 
                visited[itr -> to] = true; push(itr -> to, Ans[v]);
            }
        }
    }

    for(int i = 0; i < n; ++i) Output.write(Ans[i]);
    return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:79:22: error: 'memset' is not a member of 'std'
   79 |     Lis[0] = 0; std::memset(Lis + 1, 0x7f, sizeof(Lis + 1));
      |                      ^~~~~~
a.cc:91:64: error: 'INT32_MAX' was not declared in this scope
   91 |                 Restore[v].index = value + 1; Restore[v].val = INT32_MAX;
      |                                                                ^~~~~~~~~
a.cc:4:1: note: 'INT32_MAX' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    3 | #include <utility>
  +++ |+#include <cstdint>
    4 |