#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
const int MAXN = 2e5 + 7;
const int MAXK = 19;
int depth[MAXN];
int skok[MAXN][MAXK];
vector<int> g[MAXN];
int P[MAXN];
int ojc[MAXN];
ll ans[MAXN];
int find(int v) {
int pom = v;
while (ojc[pom] != pom) {
pom = ojc[pom];
}
while (ojc[v] != v) {
int pam = ojc[v];
ojc[v] = pom;
v = pam;
}
return v;
}
void dfs(int v, int last) {
depth[v] = depth[last] + 1;
skok[v][0] = last;
for (int k = 1; k < MAXK; k++) {
skok[v][k] = skok[skok[v][k - 1]][k - 1];
}
for (auto syn: g[v]) {
if (syn == last) continue;
dfs(syn, v);
}
}
int lca(int a, int b) {
if (depth[a] > depth[b]) {
swap(a, b);
}
int k = MAXK - 1;
while (depth[a] < depth[b]) {
if ((depth[b] - (1 << k)) < depth[a]) {
}
else {
b = skok[b][k];
}
k--;
}
if (a == b) {
return a;
}
k = MAXK - 1;
while (skok[a][0] != skok[b][0]) {
if (skok[a][k] != skok[b][k]) {
a = skok[a][k];
b = skok[b][k];
}
k--;
}
return skok[a][0];
}
void solve() {
rep(i, MAXN) {
ojc[i] = i;
}
int n;
cin >> n;
pair<int, int> T[n];
rep(i, n) {
int p;
cin >> p;
P[i + 1] = p;
T[i] = {p, i + 1};
}
rep(i, n - 1) {
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
dfs(1, 1);
sort(T, T + n);
ll odp = 0;
rep(i, n) {
int v = T[i].nd;
for (auto syn: g[v]) {
if (P[syn] < P[v]) {
int w = find(syn);
ll odl = depth[w] + depth[v] - 2 * depth[lca(w, v)];
ans[v] = max(ans[v], odl + ans[w]);
ojc[w] = v;
}
}
odp = max(odp, ans[v]);
}
cout << odp << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
# | 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... |