+ Problem : https://marisaoj.com/problem/276

Để giải quyết vấn đề, chúng ta cần biết tới thuật toán tìm LIS trong O(n * log(n)) và kĩ thuật small-to-large.

Nhận xét :
+ Tại mỗi cây con gốc u, việc chọn 2 phần tử ở 2 nhánh sẽ không ảnh hưởng gì nhau.
+ Nếu chọn u thì ta sẽ trở thành bài toán LIS trên mảng.
+ Kết hợp với kĩ thuật "cute-lis" ta có thể giải quyết bài toán trong n * log^2(n).

Sol : Tại mỗi cây con gốc u ta sẽ thêm tất cả phần tử tại multiset của các nhánh con vào u. Đối với u thì ta sẽ thực hiện như việc tìm LIS.

Code mẫu :

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second

bool vis[100001];
vector<ll> adj[100001];
ll a[100001];
multiset<ll> se[100001]; 
ll n;

void dfs(ll u){
	if(vis[u]) return;
	vis[u]=true;
	ll cur_lis = 0;
	for (int v:adj[u]){
		if (!vis[v]){
			dfs(v);
			if(se[u].size() < se[v].size()){
				se[u].swap(se[v]);
			}
			for (auto i : se[v]) se[u].insert(i);
		}
	}
	se[u].insert(a[u]);
	auto it = se[u].find(a[u]);
	it++;
	if(it!=se[u].end()){
		se[u].erase(it);
	}
}

void inp(){
	cin >> n;
	for (int i=1;i<=n;i++) {
		cin >> a[i];
	}
	for (int i=1;i<n;i++){
		ll u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void solve(){
	inp();
	memset(vis , false ,sizeof vis);
	dfs(1);
	cout << se[1].size();
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}