stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<vector>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include<cstdint>

#include<cstdlib>

#include<functional>



int const MAXN = 2e5;

int const MAXNN = 1<<18;

int a[MAXN], ans[MAXN], N;

std::vector<int> G[MAXN];



template<typename T, int NN>

struct bit {

  typedef std::function<T(T,T)> OP;

  T data_[NN]; // 0-base

  OP& op_;

  T e_;

  std::stack<std::vector<std::pair<int,T>>> ul_;

  bit(OP& op, T e) : op_(op), e_(e) { std::fill_n(data_, NN, e_); }

  int lb(int i){ return i&-i; }

  T query(int i) { // 1-base

    T res = e_;

    while(i > 0) { res = op_(res, data_[i-1]); i -= lb(i); }

    return res;

  }

  void add(int i, T const& v) { // 1-base

    std::vector<std::pair<int,T>> save;

    while(i <= NN) {

      save.emplace_back(i-1, data_[i-1]);

      data_[i-1] = op_(data_[i-1], v);

      i += lb(i);

    }

    ul_.push(save);

  }

  void undo() {

    std::vector<std::pair<int,T>>& save = ul_.top();

    for(auto p: save) data_[p.first] = p.second;

    ul_.pop();

  }

};

bit<int, MAXNN>::OP op = [](int x, int y){ return std::max(x, y); };

bit<int, MAXNN> max_bit(op, 0);



void dfs(int v, int p) {

  max_bit.add(a[v], max_bit.query(a[v]-1)+1);

  ans[v] = max_bit.query(MAXN);

  for(auto c: G[v]) if(c != p) dfs(c, v);

  max_bit.undo();

}



int main() {

  std::cin >> N;

  for(int i = 0; i < N; ++i) std::cin >> a[i];

  

  // compress a[]

  std::set<int> s(a, a+N);

  std::map<int,int> m;

  int fv = 0;

  for(int v: s) m[v] = ++fv;

  for(int i = 0; i < N; ++i) a[i] = m[a[i]];

  

  for(int i = 0; i < N-1; ++i) {

    int u, v; std::cin >> u >> v; --u; --v;

    G[u].push_back(v);

    G[v].push_back(u);

  }

  dfs(0, -1);

  for(int i = 0; i < N; ++i) std::cout << ans[i] << "\n";

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 7.539456012017604x):
#include<iostream>

#include<vector>

#include<algorithm>



int const INF = 1024102410;

int N;





int main() {

  std::cin >> N;

  

  std::vector<int> a(N);

  for(int i = 0; i < N; ++i) std::cin >> a[i];

  

  std::vector<std::vector<int>> G(N);

  for(int i = 0; i < N-1; ++i) {

    int u, v; std::cin >> u >> v; --u; --v;

    G[u].push_back(v);

    G[v].push_back(u);

  }

  

  std::vector<int> dp(N, INF), ans(N);

  auto dfs = [&](auto &&f, int v, int p)->void {

    auto pos = std::lower_bound(dp.begin(), dp.end(), a[v]);

    auto val = *pos;

    *pos = a[v];

    ans[v] = std::lower_bound(dp.begin(), dp.end(), INF) - dp.begin();

    for(auto c: G[v]) if(c != p) f(f, c, v);

    *pos = val;

  };

  

  dfs(dfs, 0, -1);

  for(auto v: ans) std::cout << v << "\n";

  return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int dp[200005];

vector<int> G[200005];

int n;

int a[200005];

int ans[200005];

const int inf = 0x3f3f3f3f;

void dfs(int u,int p){

	int ind = (int)(lower_bound(dp,dp+n,a[u]) - dp);

	int cnt = dp[ind];

	dp[ind] = a[u];

	ans[u] = (int)(lower_bound(dp,dp+n,inf) - dp);

	for(int i:G[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	//undo

	dp[ind] = cnt;

}

int main(){

	cin>>n;

	for(int i=0;i<n;i++){

		cin>>a[i];

	}

	for(int i=0;i<n-1;i++){

		int t1,t2;

		cin>>t1>>t2;

		t1--,t2--;

		G[t1].push_back(t2);

		G[t2].push_back(t1);

	}

	fill(dp,dp+n+2,inf);

	dfs(0,-1);

	for(int i=0;i<n;i++) cout<<ans[i]<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 6.343688747256044x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

int n;

int v[200005];

int dp[200005];

int f[200005];

vector<vector<int>> g;

void dfs(int p, int u) {

    int pos = lower_bound(f, f+n, v[p]) - f;

    int t = f[pos];

    f[pos] = v[p]; 

    dp[p] = lower_bound(f, f+n, inf) - f;

    for(auto i:g[p]) {

        if(i!=u)

        dfs(i, p);

    }

    f[pos] = t;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n;

    g.resize(n+1);

    for(int i=0;i<n;i++) cin>>v[i];

    fill(f,f+n+2,inf);

    for(int i=1;i<n;i++) {

        int x, y;

        cin>>x>>y;

        x--; y--;

        g[x].push_back(y);

        g[y].push_back(x);

    }

    dfs(0, -1);

    for(int i=0;i<n;i++) cout<<dp[i]<<endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long;

using P = pair<int,int>;

 

const int MAX_N = 200005;

const int INF = 1001001001;

 

vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

 

void dfs(int v, int p=-1) {

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if (p != -1) ans[v] = max(ans[v], ans[p]);

  for (int u : to[v]) {

    if (u == p) continue;

    dfs(u, v);

  }

  dp[i] = old;

}

 

int main() {

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i,n) cin >> a[i];

  rep(i,n-1) {

    int u, v;

    cin >> u >> v;

    --u; --v;

    to[v].push_back(u);

    to[u].push_back(v);

  }

  rep(i,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  dfs(0);

  rep(i,n) cout << ans[i] << endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.845384187821421x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(MAX_N);

  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;



vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

void dfs(int v, int p=-1){

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if(p != -1) ans[v] = max(ans[v], ans[p]); //exclude first turn

  

  	for(int u : to[v]){

       if(u == p) continue;  //parent

       dfs(u, v);

  	}

  //roll back

  	dp[i] = old;

}



int main(){

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }



  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    --u, --v;

    to[u].push_back(v);

    to[v].push_back(u);

  }



  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

    

    

// Faster C++ solution for the same problem (measured speedup: 3.8453848357570255x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(MAX_N);

  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }
// Slower C++ solution:
#include <bits/stdc++.h>

#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;

using ll = long long;

using P = pair<int,int>;

 

const int MAX_N = 200005;

const int INF = 1001001001;

 

vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

 

void dfs(int v, int p=-1) {

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if (p != -1) ans[v] = max(ans[v], ans[p]);

  for (int u : to[v]) {

    if (u == p) continue;

    dfs(u, v);

  }

  dp[i] = old;

}

 

int main() {

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i,n) cin >> a[i];

  rep(i,n-1) {

    int u, v;

    cin >> u >> v;

    --u; --v;

    to[v].push_back(u);

    to[u].push_back(v);

  }

  rep(i,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  dfs(0);

  rep(i,n) cout << ans[i] << endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 7.225593266629089x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;



vector<int> a, ans;

vector<int> to[MAX_N];

int dp[MAX_N];

void dfs(int v, int p=-1){

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if(p != -1) ans[v] = max(ans[v], ans[p]); //exclude first turn

  

  	for(int u : to[v]){

       if(u == p) continue;  //parent

       dfs(u, v);

  	}

  //roll back

  	dp[i] = old;

}



int main(){

  int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }



  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    --u, --v;

    to[u].push_back(v);

    to[v].push_back(u);

  }



  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

    

    

// Faster C++ solution for the same problem (measured speedup: 7.225594484119699x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(MAX_N);

  rep(i ,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }

    

    

// Faster C++ solution for the same problem (measured speedup: 1.8790302642615029x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)

using ll = long long;

const int INF=1001001001;

const int MAX_N = 200005;

 

vector<int> a, ans, dp;

vector<vector<int>> to;

void dfs(int s, int p=-1){

 int i = lower_bound( dp.begin(), dp.end(), a[s]) - dp.begin();

  int old = dp[i];

  dp[i] = a[s];

  ans[s] = i;

  if(p != -1) ans[s] = max(ans[s], ans[p]); //exclude first turn

  

  	for(int t : to[s]){

       if(t == p) continue;  //parent

       dfs(t, s);

  	}

  //roll back

  	dp[i] = old;

}

 

int main(){

	int n;

  cin >> n;

  a = ans = vector<int>(n);

  rep(i, n){

    cin >> a[i];    

  }

  to = vector<vector<int>>(n);

  rep(i, n-1){

    int u, v;

    cin >> u >> v;

    u--, v--;

    to[u].push_back(v);

    to[v].push_back(u);

  }

 

  dp = vector<int>(n);

  rep(i ,n) dp[i] = INF;

  dp[0] = -INF;

  

  dfs(0);  

  rep(i, n){

    cout << ans[i] << endl;

  }      

    return 0;

  }
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fi first

#define se second

#define pb push_back

#define forn(i,n) for(int i=0;i<(n);i++)

#define for1(i,n) for(int i=1;i<=n;i++)

#define forr(i,n) for(int i=n;i>=0;i--)

#define all(x) x.begin(), x.end()

const int MAXN = 2e5 +5;



void fio(){

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

}



vector<LL> ar(MAXN);

vector<vector<LL> > adj(MAXN);

LL BIT[MAXN];



LL max(LL a, LL b){

	return a>b?a:b;

}



int n;

int t[2*MAXN];



void modify(int p, int value) {  

  for (t[p += n+1] = value; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);

}



int query(int l, int r) { 

  int res = 0;

  for (l += n+1, r += n+1; l < r; l >>= 1, r >>= 1) {

    if (l&1) res = max(res,t[l++]);

    if (r&1) res = max(res,t[--r]);

  }

  return res;

}



int an[MAXN];



void dfs(int u,int p){

	int old = query(ar[u], ar[u]+1);

	int	x = query(0, ar[u]); 

	int value = x + 1; 

	

	//cout<<u<<" "<<ar[u]<<" "<<x<<endl;

	modify(ar[u], max(value,old));

	an[u] = query(0,n+1);

	for(auto i:adj[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	modify(ar[u], old);

		//cout<<u<<" "<<p<<endl;

}



int main(){

  fio();

  cin>>n;

  vector<LL> v(n);

  set<LL> s;

  forn(i,n) {

  	cin>>v[i];

  	s.insert(v[i]);

  }

  int in = 0;

  map<LL,LL> mp;

  for(auto i:s){

  	mp[i] = ++in;

  }

  forn(i,n){

  	ar[i+1] = mp[v[i]];

  }

  forn(i,n-1){

  	int u, v; cin>>u>>v;

  	adj[v].pb(u);

  	adj[u].pb(v);

  }

  

  // for1(i,n) cout<<ar[i]<<" ";x

  // cout<<endl;

  

  dfs(1,0);

  for1(i,n) cout<<an[i]<<endl;



  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2625199010074981x):
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define fi first

#define se second

#define pb push_back

#define forn(i,n) for(int i=0;i<(n);i++)

#define for1(i,n) for(int i=1;i<=n;i++)

#define forr(i,n) for(int i=n;i>=0;i--)

#define all(x) x.begin(), x.end()

const int MAXN = 2e5 +5;



void fio(){

  ios::sync_with_stdio(0);

  cin.tie(0);

  cout.tie(0);

}





vector<vector<int>> adj(MAXN);



LL max(LL a, LL b){

	return a>b?a:b;

}



int n;

vector<LL> v;

int an[MAXN];

vector <int> lc;



void dfs(int u,int p){

	auto x = upper_bound(all(lc), v[u]) - lc.begin();

	int ch = -1;

	int val;

	if(x >=1 && lc[x-1]!=v[u] || x == 0){

		ch = x;

		val = lc[x];

		lc[x] = v[u];

	}

	an[u] = lower_bound(all(lc), INT_MAX) - lc.begin();

	for(auto i:adj[u]){

		if(i!=p){

			dfs(i,u);

		}

	}

	if(ch!=-1) lc[x] = val;

}



int main(){

  fio();

  cin>>n;

  set<LL> s;

  forn(i,n) {

  	int x; cin>>x;

  	v.pb(x);

  }

  lc.resize(n+1);

  forn(i,n+1) lc[i] = INT_MAX;

  forn(i,n-1){

  	int u, x; cin>>u>>x;

  	u--, x--;

  	adj[x].pb(u);

  	adj[u].pb(x);

  } 

  dfs(0,-1);

  forn(i,n) cout<<an[i]<<endl;



  return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

#include <queue>

#include <set>

#include <map>



using namespace std;

typedef long long ll;

int N;

ll a[200005];

int u[200005], v[200005];



ll dp[200005];

vector<int> G[200005];

bool used[200005];

int ans[200005];



const ll INF = 2e15;



void dfs(int v, int d){

    used[v] = true;

    auto p = lower_bound(dp, dp+N+4, a[v]);

    int dif = p-dp;

    ll pre = dp[dif];

    dp[dif] = min(a[v], dp[dif]);

    ans[v] = lower_bound(dp, dp+N+4, INF)-dp;

    for(int to : G[v]){

        if(!used[to]){

            dfs(to, d+1);

        }

    }

    dp[dif] = pre;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << setprecision(10) << fixed;

    cin >> N;

    for(int i = 0; i < N; i++) cin >> a[i];

    for(int i = 0; i < N-1; i++){

        cin >> u[i] >> v[i];

        u[i]--; v[i]--;

        G[u[i]].push_back(v[i]);

        G[v[i]].push_back(u[i]);

    }

    for(int i = 0; i <= 200004; i++) dp[i] = INF+i; 

    // dp[0] = a[0];

    // ans[0] = 1;

    dfs(0, 1);

    for(int i = 0; i < N; i++) cout << ans[i] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.2831334918067174x):
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <vector>

#include <queue>

#include <set>

#include <map>



using namespace std;

typedef long long ll;

int N;

ll a[200005];

int u[200005], v[200005];



ll dp[200005];

vector<int> G[200005];

bool used[200005];

int ans[200005];



const ll INF = 2e15;



void dfs(int v){

    used[v] = true;

    auto p = lower_bound(dp, dp+N+2, a[v]);

    int dif = p-dp;

    ll pre = dp[dif];

    dp[dif] = min(a[v], dp[dif]);

    ans[v] = lower_bound(dp, dp+N+2, INF)-dp;

    for(int to : G[v]){

        if(!used[to]){

            dfs(to);

        }

    }

    dp[dif] = pre;

}



int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout << setprecision(10) << fixed;

    cin >> N;

    for(int i = 0; i < N; i++) cin >> a[i];

    for(int i = 0; i < N-1; i++){

        cin >> u[i] >> v[i];

        u[i]--; v[i]--;

        G[u[i]].push_back(v[i]);

        G[v[i]].push_back(u[i]);

    }

    for(int i = 0; i <= N+2; i++) dp[i] = INF; 

    dfs(0);

    for(int i = 0; i < N; i++) cout << ans[i] << endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

using ll = long long;



template <typename T>

struct SegmentTree {

  int N;

  T init;

  vector<T> dat;

  SegmentTree(int n, T init) : init(init) {

    N = 1;

    while (N < n) N *= 2;

    dat.assign(2*N-1, init);

  }

  void update(int i, T x) {

    i += N - 1;

    dat[i] = x;

    while (i > 0) {

      i = (i - 1) / 2;

      dat[i] = max(dat[i*2+1], dat[i*2+2]);

    }

  }

  // a <= x < b

  T query(int a, int b) { return query(a, b, 0, 0, N); }

  T query(int a, int b, int i, int l, int r) {

    if(r <= a || b <= l) return init;

    if(a <= l && r <= b) return dat[i];

    T vl = query(a, b, i*2+1, l, (l+r)/2);

    T vr = query(a, b, i*2+2, (l+r)/2, r);

    return max(vl, vr);

  }

};



SegmentTree<int>st(200009,0);

int a[200009];

vector<int>to[200009];

int ans[200009];

map<int,int>mp;



void dfs(int v,int p=-1){

  int i=mp[a[v]];

  int temp=st.query(i,i+1);

  st.update(i,st.query(0,i)+1);

  ans[v]=st.query(0,200000);

  for(auto u:to[v]){

    if(u==p)continue;

    dfs(u,v);

  }

  st.update(i,temp);

}



int main(){

  int n;

  cin>>n;

  vector<int>b;

  rep(i,n){

    cin>>a[i];

    b.push_back(a[i]);

  }

  sort(b.begin(),b.end());

  b.erase(unique(b.begin(),b.end()),b.end());

  rep(i,b.size()){

    mp[b[i]]=i;

  }

  rep(i,n-1){

    int s,t;

    cin>>s>>t;

    s--;t--;

    to[s].push_back(t);

    to[t].push_back(s);

  }

  dfs(0);

  rep(i,n){

    cout<<ans[i]<<endl;

  }

  return(0);

}


// Faster C++ solution for the same problem (measured speedup: 1.1848497811922565x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)

#define chmax(a, b) a = max(a, b)

#define chmin(a, b) a = min(a, b)

#define fi first

#define se second

#define INF 1000000009

#define LLINF 1000000000000000009LL

#define MAX_N 200009

using ll = long long;



vector<int> a;

vector<int> to[MAX_N];

int dp[MAX_N];

int ans[MAX_N];



void dfs(int v, int p=-1) {

  int i = lower_bound(dp, dp+MAX_N, a[v]) - dp;

  int old = dp[i];

  dp[i] = a[v];

  ans[v] = i;

  if (p != -1) ans[v] = max(ans[v], ans[p]);

  for (auto u : to[v]) {

    if (u == p) continue;

    dfs(u, v);

  }

  dp[i] = old;

}



int main() {

  int n;

  cin >> n;

  a = vector<int>(n);

  rep(i,n) cin >> a[i];

  rep(i,n-1) {

    int s, t;

    cin >> s >> t;

    s--; t--;

    to[s].push_back(t);

    to[t].push_back(s);

  }

  rep(i,MAX_N) dp[i] = INF;

  dp[0] = -INF;

  dfs(0);

  rep(i,n) {

    cout << ans[i] << endl;

  }

  return(0);

}