#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 2e5 + 1;
struct str {
int a, i;
} v[nmax];
bool cmp(str x, str y) {
return x.a < y.a;
}
vector<int> adj[nmax];
set<int> sz[nmax];
int root[nmax], d[nmax], dp[nmax], back[nmax], to[nmax];
int up[nmax][20];
int find(int a) {
if(root[a] == a) {
return a;
}
return root[a] = find(root[a]);
}
void unite(int a, int b) {
if(a == b) {
return;
}
if(sz[a].size() < sz[b].size()) {
swap(a, b);
}
for(auto it : sz[b]) {
sz[a].insert(it);
}
sz[b].clear();
root[b] = a;
}
void dfs(int i, int tata = 0) {
up[i][0] = tata;
for(int j = 1; (1 << j) <= d[i]; j++) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
for(auto it : adj[i]) {
if(it != tata) {
d[it] = d[i] + 1;
dfs(it, i);
}
}
}
int lift(int a, int nr) {
for(int i = 0; (1 << i) <= nr; i++) {
if((1 << i) & nr) {
a = up[a][i];
}
}
return a;
}
int get_dist(int a, int b) {
if(d[a] > d[b]) {
swap(a, b);
}
int l = 0, r = d[a], ans = 0;
while(l <= r) {
int mid = (l + r) / 2;
if(l == -1) {
exit(0);
}
//while(true);
if(lift(a, mid) == lift(b, mid + d[b] - d[a])) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return 2 * ans + d[b] - d[a];
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> v[i].a;
back[v[i].a] = i;
v[i].i = i;
root[i] = i;
}
sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; i++) {
to[v[i].i] = i;
}
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1);
for(int i = 1; i <= n; i++) {
for(auto it : adj[v[i].i]) {
if(v[to[it]].a < v[i].a) {
if(sz[find(it)].size() != 0) {
int x = back[*sz[find(it)].rbegin()];
dp[v[i].i] = max(dp[v[i].i], dp[x] + get_dist(v[i].i, x));
// cout << v[i].i << " " << x << " " << dp[v[i].i] << '\n';
}
unite(find(it), find(v[i].i));
}
}
sz[find(v[i].i)].insert(v[i].a);
}
cout << dp[back[n]];
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... |