Submission #12625049

---

Source Code Expand

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

ll inf = 1e18;
int N;
vector<ll> A;
vector<vector<int>> edge;
vector<ll> ans;
vector<stack<pair<ll, int>>> dp;

void dfs(int now, int pre, int premx) {
    int l = 0, r = N+1;
    while (r-l > 1) {
        int c = (l+r)/2;
        if (dp[c].top().first < A[now]) l = c;
        else r = c;
    }
    int mx = max(premx, l+1);
    ans[now] = mx;
    bool stacked = false;
    if (dp[l+1].top().first > A[now]) {
        dp[l+1].push({A[now], now});
        stacked = true;
    }
    
    for (int nxt : edge[now]) {
        if (nxt == pre) continue;
        dfs(nxt, now, mx);
    }
    
    if (stacked) {
        dp[l+1].pop();
    }
    return;
}

int main() {
    cin >> N;
    A.resize(N+1);
    edge.resize(N+1);
    dp.resize(N+1);
    ans.resize(N+1, 0);
    ans[0] = 1;
    for (int i = 0; i < N; i++) cin >> A[i+1];
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dp[0].push({0, -1});
    for (int i = 1; i <= N; i++) {
        dp[i].push({inf, -1});
    }
    dfs(1, -1, 0);
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Submission Info

Judge Result