Language: C++

#include <bits/stdc++.h>

using namespace std;

vector<int> values;
vector<int> answer;
vector<vector<int>> adj;
vector<map<int,int>> lis;

void dfs(int v, int p){
   int loc = -1;
   
   if(lis.size() == 0){
      map<int,int> temp;
      lis.push_back(temp);
      lis[0].insert(values[v],1);
      loc = 0;
   } 
   else if(values[v] <= lis[0].begin()->first){
          //add to first list
      if(lis[0].find(values[v]) != lis[0].end()){
         lis[0].insert(values[v],lis[0][values[v]]+1);
      } 
      else {
         lis[0].insert(values[v],1);
      }
      loc = 0;
   } 
   else if(values[v] > lis[lis.size()-1].begin() -> first){
         //add
      map<int,int> temp;
      lis.push_back(temp);
      lis[lis.size()-1].insert(values[v],1);
      loc = lis.size()-1;
   } 
   else {
      int l = 0;
      int r = lis.size()-1;
      int ans = r;
         
      while(l <= r){
         int mid = l + (r-l)/2;
            
         if(values[v] <= lis[mid].begin() -> first){
            r = mid-1;
            ans = mid;
         } 
         else {
            l = mid+1;
               
         }
      }
         
      if(lis[ans].find(values[v]) != lis[ans].end()){
         lis[ans].insert(values[v],lis[ans][values[v]]+1);
      } 
      else {
         lis[ans].insert(values[v],1);
      }
      loc = ans;
   }
   
   answer[v] = lis.size();
      
   for(auto nei : adj[v]){
      if(nei == p) 
         continue;
      dfs(nei,v);
   }
      
      //remove
   if(lis[loc][values[v]] > 1){
      lis[loc].insert(values[v],lis[loc][values[v]]-1);
   } 
   else {
      lis[loc].erase(values[v]);
      if(lis[loc].size()==0){
         lis.pop_back();
      }
   }
      
}



int main(){
   ios::sync_with_stdio(false);
   cin.tie(0);
   
   int n;
   cin >> n;
   
   values.push_back(0);
   for(int k = 1; k <= n; k++){
      cin >> values[k];
   }
   
   for(int k = 0; k <= n; k++){
      vector<int> temp;
      adj.push_back(temp);
   }
   
   for(int k = 0; k < n-1; k++){
      int a,b;
      cin >> a >> b;
      
      adj[a].push_back(b);
      adj[b].push_back(a);
   }
   
   dfs(1, -1);
   
   for(int k = 1; k <= n; k++){
      cout << answer[k] << endl;
   }
   
   
   
   
   return 0;
}

Compiler output:
In file included from /usr/include/c++/14/map:63,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:152,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_map.h: In instantiation of 'void std::map<_Key, _Tp, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]':
a.cc:16:20:   required from here
   16 |       lis[0].insert(values[v],1);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_map.h:943:38: error: no matching function for call to 'std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique(int&, int&)'
  943 |         { _M_t._M_insert_range_unique(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/map:62:
/usr/include/c++/14/bits/stl_tree.h:1096:9: note: candidate: 'template<class _InputIterator> std::__enable_if_t<((bool)std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value)> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _Key = int; _Val = std::pair<const int, int>; _KeyOfValue = std::_Select1st<std::pair<const int, int> >; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
 1096 |         _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1096:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<((bool)std::is_same<std::pair<const int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value), void> std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/14/bits/stl_map.h:943:31:   required from 'void std::map<_Key, _Tp, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
  943 |         { _M_t._M_insert_range_unique(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
a.cc:16:20:   required from here
   16 |       lis[0].insert(values[v],1);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1095:58: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
 1095 |         __enable_if_t<__same_value_type<_InputIterator>::value>
      |                                                          ^~~~~
/usr/include/c++/14/bits/stl_map.h: In instantiation of 'void std::map<_Key, _Tp, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]':
a.cc:16:20:   required from here
   16 |       lis[0].insert(values[v],1);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1105:9: note: candidate: 'template<class _InputIterator> std::__enable_if_t<((bool)(! std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value))> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _Key = int; _Val = std::pair<const int, int>; _KeyOfValue = std::_Select1st<std::pair<const int, int> >; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
 1105 |         _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |         ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1105:9: note:   template argument deduction/substitution failed:
/usr/include/c++/14/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<((bool)(! std::is_same<std::pair<const int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value)), void> std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/14/bits/stl_map.h:943:31:   required from 'void std::map<_Key, _Tp, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
  943 |         { _M_t._M_insert_range_unique(__first, __last); }
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
a.cc:16:20:   required from here
   16 |       lis[0].insert(values[v],1);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_tree.h:1104:59: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
 1104 |         __enable_if_t<!__same_value_type<_InputIterator>::value>
      |                                                           ^~~~~