Language: C++

#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")

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

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;

char* output = Input.Input;
constexpr int digit = 4;
constexpr int MAX_D_SIZE = 100'00; //'
struct NoName{
    struct Mike{
        int str;
        int dig;
        constexpr Mike(void):str(), dig(){}
    };
    Mike S[MAX_D_SIZE];
    int T[MAX_D_SIZE];
    constexpr NoName(void): S(), T(){
        char P[8]{}, Q[8]{};
        for(int i = 0; i < MAX_D_SIZE; ++i){
            int t = i;
            char* ptr = P;
            while(t){ S[i].dig++; *(ptr++) = '0' ^ (t % 10); t /= 10; }
            for(int j = 0, j2 = digit - 1; j < digit; ++j, --j2){
                Q[j2] = P[j] ? P[j] : '0';
            }
            --ptr; char* ptr2 = P;
            while(ptr2 < ptr){
                const char c = *ptr; 
                *(ptr--) = *ptr2; *(ptr2++) = c;
            }
            for(int j1  = 0, j2 = 0; j1 < digit; ++j1, j2 += 8){
                S[i].str |= (int)(P[j1]) << j2; P[j1] = 0;
                T[i]     |= (int)(Q[j1]) << j2; Q[j1] = 0;
            }
        }
    }
};
constexpr NoName Da;
 
inline void writeBuffer(const int& n){
    if(n < MAX_D_SIZE){
        *(int*)(output) = Da.S[n].str;
        output += Da.S[n].dig;
    }
    else{
        const int s = n / MAX_D_SIZE, t = n % MAX_D_SIZE;
        *(int*)(output) = Da.S[s].str;
        output += Da.S[s].dig;
        *(int*)(output) = Da.T[t];
        output += digit;
    }    
    *(output++) = '\n';
}

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

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

edge Edge[2 * MAX_N + 1];
edge* begin[MAX_N + 1];
edge* e_ptr = Edge;

struct stack_type{
    int vertex;
    int val;
};
stack_type Stack[2 * MAX_N + 3];
stack_type * stack = Stack;

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

constexpr int the_mask = 1 << 31;
int W[2];

int main(void){
    int n = Input.getint();
    A[1] = Input.getint();
    for(int i = 2; i <= n; ++i) A[i] = Input.getint() | the_mask;
    Lis[0] = 0; std::memset(Lis + 1, 0x7f, sizeof(Lis + 1));
    for(int i = 1; i < n; ++i){
        int u = Input.getint(), v = Input.getint();
        e_ptr -> to = v; e_ptr -> next = begin[u]; begin[u] = e_ptr++;
        e_ptr -> to = u; e_ptr -> next = begin[v]; begin[v] = e_ptr++;
    }
    stack -> vertex = 1; ++stack;
    while((stack--) != Stack){
        const int v = stack -> vertex, value = stack -> val;
        if(value ^ (-1)){
            stack -> vertex = v, stack -> val = -1; ++stack;
            if(Lis[value] < A[v]){
                const int&& tmp = value + 1;
                Restore[v].index = tmp; Restore[v].val = INT32_MAX;
                Lis[tmp] = A[v]; A[v] = tmp;
            }
            else{
                W[0] = value, W[1] = 0;
                while(W[0] - W[1] > 1){
                    const int&& mid = (W[0] + W[1]) >> 1;
                    W[Lis[mid] < A[v]] = mid;
                }
                Restore[v].index = W[0]; Restore[v].val = Lis[W[0]];
                Lis[W[0]] = A[v]; A[v] = value;
            }
            for(edge* itr = begin[v]; itr; itr = itr -> next) if(A[itr -> to] & the_mask){ 
                A[itr -> to] ^= the_mask; stack -> vertex = itr -> to, stack -> val = A[v]; ++stack;
            }
        }
        else{ Lis[Restore[v].index] = Restore[v].val; }
    }
    for(int i = 1; i <= n; ++i) writeBuffer(A[i]);
    fwrite_unlocked(Input.Input, sizeof(char), output - Input.Input, stdout);
    return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:117:58: error: 'INT32_MAX' was not declared in this scope
  117 |                 Restore[v].index = tmp; Restore[v].val = INT32_MAX;
      |                                                          ^~~~~~~~~
a.cc:7:1: note: 'INT32_MAX' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    6 | #include <cstring>
  +++ |+#include <cstdint>
    7 |