#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200009;
vector < int > g[N], q[N];
ll n, h[N], w[N], f[N], s[N], lnk[N];
int get(int v) { return (v == lnk[v] ? v : lnk[v] = get(lnk[v])); }
void unite(int u, int v) {
u = get(u), v = get(v);
if (u == v) return;
lnk[u] = v;
s[v] = max(s[v], s[u]);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h[i];
w[h[i]] = i;
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) lnk[i] = i;
for (int i = 1; i <= n; i++) {
int v = w[i];
for (auto u : g[v]) q[s[get(u)]].push_back(h[v]);
s[v] = h[v];
for (auto u : g[v]) if (h[u] < h[v]) unite(u, v);
}
for (int i = 1; i <= n; i++) {
for (auto j : q[i]) f[j] = max(f[j], f[i] + abs(w[i] - w[j]));
}
cout << f[n];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |