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>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
#define F first
#define S second
using namespace std;
const int maxn=200005;
int n,a,b,p[maxn][25],h[maxn];
ll dep[maxn],dp[maxn];
vi g[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
for(int i=0;i<n;i++) cin >> h[i];
for(int i=1;i<n;i++){
cin >> a >> b;
a--,b--;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
function<void(int,int)> dfs=[&](int x,int pre){
dep[x]=dep[pre]+1;
p[x][0]=pre;
for(int i=1;i<25;i++) p[x][i]=p[p[x][i-1]][i-1];
for(int u:g[x]){
if(u==pre) continue;
dfs(u,x);
}
};
dfs(0,0);
function<int(int,int)> lca=[&](int x,int y){
if(dep[x]>dep[y]) swap(x,y);
int tmp=dep[y]-dep[x],i=0;
while(tmp){
if(tmp&1) y=p[y][i];
i++,tmp>>=1;
}
if(x==y) return x;
for(int j=24;j>=0;j--){
if(p[x][j]!=p[y][j]){
x=p[x][j];
y=p[y][j];
}
}
return p[x][0];
};
vi ord(n),pa(n);
iota(all(ord),0);
iota(all(pa),0);
sort(all(ord),[](int i,int j){return h[i]<h[j];});
function<int(int)> get=[&](int x){
return x==pa[x] ? x : pa[x]=get(pa[x]);
};
function<ll(int,int)> get_dist=[&](int x,int y){
return dep[x]+dep[y]-2*dep[lca(x,y)];
};
for(int i:ord){
for(int j:g[i]){
if(h[i]>h[j]){
dp[i]=max(dp[i],dp[get(j)]+get_dist(i,get(j)));
pa[get(j)]=i;
}
}
}
cout << dp[ord[n-1]] << "\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... |