题解 | #树上上升序列#

C++ 有向图 + 记忆化搜索

• 建立有向图：u，v为树上的一条边

  • 当v的权值大于u的权值时，增加一条u到v的边
  • 当u的权值大于v的权值时，增加一条v到u的边

• dp[u] : 以u为起始顶点的最长递增路径长度。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int n, w[maxn], ids[maxn], dp[maxn];
vector<int> g[maxn];

// 返回以u为起始点的最长递增路径长度
int dfs(int u) {
    if (dp[u] != -1) return dp[u];
    int cur = 0;
    for (int v : g[u]) {
        cur = max(cur, dfs(v));
    }
    return dp[u] = cur + 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) scanf("%d", &w[i]);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (w[v] > w[u]) g[u].push_back(v);
        if (w[u] > w[v]) g[v].push_back(u);
    }
    memset(dp, -1, sizeof(dp));
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dfs(i));
    }        
    cout << ans << endl;
    return 0;
}