This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
vector<int> q[200100];
int p[200100], sz[200100];
ll mx[200100];
ll dp[200100];
int jmp[200100][30];
int tin[200100], tout[200100], timer = 0;
int h[200100];
int pos[200100];
int a[200100];
void dfs(int v, int p){
jmp[v][0] = p;
tin[v] = ++timer;
for(int to: q[v]){
if(to == p) continue;
h[to] = h[v] + 1;
dfs(to, v);
}
tout[v] = ++timer;
}
bool upper(int a, int b){
if(a == 0) return 1;
return tin[a] <= tin[b] and tout[a] >= tout[b];
}
int lca(int a, int b){
if(upper(a, b)) return a;
if(upper(b, a)) return b;
for(int i=20; i>=0; i--){
if(upper(jmp[a][i], b)) continue;
a = jmp[a][i];
}
return jmp[a][0];
}
int dist(int a, int b){
return h[a] + h[b] - 2 * h[lca(a, b)];
}
int get(int a){
if(p[a] == a) return a;
return p[a] = get(p[a]);
}
void un(int x, int y){
x = get(x);
y = get(y);
if(x == y) return;
if(sz[x] > sz[y]) swap(x, y);
p[y] = p[x];
sz[x] += sz[y];
if(a[mx[x]] < a[mx[y]]) mx[x] = mx[y];
}
void solve(){
int n;
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
p[i] = i;
mx[i] = i;
pos[a[i]] = i;
sz[i] = 1;
dp[i] = 0;
}
for(int i=1; i<n; i++){
int l, r;
cin>>l>>r;
q[l].pb(r);
q[r].pb(l);
}
dfs(1, 0);
for(int k=1; k<=20; k++){
for(int i=1; i<=n; i++){
if((1 << k) > n) break;
jmp[i][k] = jmp[jmp[i][k - 1]][k - 1];
}
}
for(int i=1; i<=n; i++){
vector<int> d;
int v = pos[i];
for(int to: q[v]){
if(a[to] > i or get(to) == get(v)) continue;
to = get(to);
d.pb(mx[to]);
un(to, v);
}
//cout<<"#################\n";
//cout<<v<<'\n';
dp[v] = 0;
for(int h: d){
//cout<<h<<' ';
dp[v] = max(dp[v], dp[h] + dist(v, h));
}
//cout<<'\n';
//cout<<dp[v]<<'\n';
}
cout<<dp[pos[n]]<<'\n';;
}
int main(){
solve();
}
# | 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... |