题解 | #树上上升序列#

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
long long n, m, k, t;
int v[100005]; 
int u[100005];
unordered_map<int, vector<int>>mp;
//我们赋予这个递归函数的职责就是
//返回以x为起点的满足条件的最长路径
int dfs(int x) {
	if (u[x] != -1)return u[x]; //存在就返回
	int t = 1; //本身至少算一个点
	for (auto i : mp[x]) { 
		int mid = u[i] == -1 ? dfs(i): u[i]; //对于i这个点有没有计算过了？有的话直接返回，否则去dfs
		t = max(mid + 1, t); //取较大值，mid+1，mid是i这个点作为起点最长路径，要加上x这个点
	}
	return u[x] = t;
} 
int main() {   
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		u[i] = -1;
	}
	for (int i = 1; i < n; i++) {
		cin >> k >> t;
        //只记录有效路径，没用的路径不要记录
		if(v[k]>v[t])
			mp[t].push_back(k);
		if(v[t]>v[k])
			mp[k].push_back(t);
	} 
	int res = 0;
    // 题目没有保证所有点能够连通，可能有好几块区域
	for (int i = 1; i <= n; i++) {
		if (u[i] == -1)res = max(res, dfs(i));
	}
	cout << res << endl;

	return 0;
}