#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=2e5+5;
vector<int>adj[mxn];
int h[mxn],root,cnt[mxn],dep[mxn],to[mxn],dp[mxn];
int jump[20][mxn];
vector<pii>ord;
int cur=0;
void cntsz(int v,int pa){
cnt[v]=1;
dep[v]=dep[pa]+1;
jump[0][v]=pa;
for(auto u:adj[v]){
if(u==pa)continue;
cntsz(u,v);
cnt[v]+=cnt[u];
}
}
void build(int n){
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
jump[i][j]=jump[i-1][jump[i-1][j]];
}
}
}
int lca(int v,int u){
if(dep[v]<dep[u])swap(v,u);
int dif=dep[v]-dep[u];
for(int i=0;i<20;i++){
if(dif>>i&1){
v=jump[i][v];
}
}
if(u==v)return v;
for(int i=19;i>=0;i--){
if(jump[i][u]!=jump[i][v]){
v=jump[i][v];
u=jump[i][u];
}
}
return jump[0][v];
}
int find(int x){
return x==to[x]?x:to[x]=find(to[x]);
}
int dist(int a,int b){
return dep[a]+dep[b]-2*dep[lca(a,b)];
}
void merge(int a,int b){
a=find(a),b=find(b);
chmax(dp[b],dp[a]+dist(a,b));
to[a]=b;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
to[i]=i;
cin>>h[i];
ord.pb({h[i],i});
if(h[i]==n)root=i;
}
sort(all(ord));
for(int i=1;i<n;i++){
int a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
cntsz(root,root);
build(n);
int ans=0;
for(auto [he,x]:ord){
for(auto u:adj[x]){
if(h[u]<he){
merge(u,x);
}
}
chmax(ans,dp[x]);
}
cout<<ans<<'\n';
}
/*
input:
1 0
1 1
1 0
0 1
0 1
0 1
0 0
0 0
0 0
1 1
1 0
1 1
1 1 1
1 0 1
1 1 0
1 0 0
1 1 1
1 1 0
0 1 1
0 1 0
0 1 1
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:92:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
92 | for(auto [he,x]:ord){
| ^
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
11 |
Correct |
5 ms |
42076 KB |
Output is correct |
12 |
Correct |
5 ms |
42076 KB |
Output is correct |
13 |
Correct |
5 ms |
42076 KB |
Output is correct |
14 |
Correct |
5 ms |
42084 KB |
Output is correct |
15 |
Correct |
5 ms |
42076 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
11 |
Correct |
5 ms |
42076 KB |
Output is correct |
12 |
Correct |
5 ms |
42076 KB |
Output is correct |
13 |
Correct |
5 ms |
42076 KB |
Output is correct |
14 |
Correct |
5 ms |
42084 KB |
Output is correct |
15 |
Correct |
5 ms |
42076 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42076 KB |
Output is correct |
18 |
Correct |
7 ms |
42588 KB |
Output is correct |
19 |
Correct |
7 ms |
42708 KB |
Output is correct |
20 |
Correct |
7 ms |
42588 KB |
Output is correct |
21 |
Correct |
8 ms |
42588 KB |
Output is correct |
22 |
Correct |
7 ms |
42428 KB |
Output is correct |
23 |
Correct |
7 ms |
42588 KB |
Output is correct |
24 |
Correct |
7 ms |
42588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
11 |
Correct |
5 ms |
42076 KB |
Output is correct |
12 |
Correct |
5 ms |
42076 KB |
Output is correct |
13 |
Correct |
5 ms |
42076 KB |
Output is correct |
14 |
Correct |
5 ms |
42084 KB |
Output is correct |
15 |
Correct |
5 ms |
42076 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42076 KB |
Output is correct |
18 |
Correct |
7 ms |
42588 KB |
Output is correct |
19 |
Correct |
7 ms |
42708 KB |
Output is correct |
20 |
Correct |
7 ms |
42588 KB |
Output is correct |
21 |
Correct |
8 ms |
42588 KB |
Output is correct |
22 |
Correct |
7 ms |
42428 KB |
Output is correct |
23 |
Correct |
7 ms |
42588 KB |
Output is correct |
24 |
Correct |
7 ms |
42588 KB |
Output is correct |
25 |
Correct |
5 ms |
42076 KB |
Output is correct |
26 |
Correct |
7 ms |
42668 KB |
Output is correct |
27 |
Correct |
8 ms |
42584 KB |
Output is correct |
28 |
Correct |
8 ms |
42588 KB |
Output is correct |
29 |
Correct |
7 ms |
42588 KB |
Output is correct |
30 |
Correct |
8 ms |
42292 KB |
Output is correct |
31 |
Correct |
8 ms |
42332 KB |
Output is correct |
32 |
Correct |
9 ms |
42452 KB |
Output is correct |
33 |
Correct |
8 ms |
42328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
11 |
Correct |
5 ms |
42076 KB |
Output is correct |
12 |
Correct |
5 ms |
42076 KB |
Output is correct |
13 |
Correct |
5 ms |
42076 KB |
Output is correct |
14 |
Correct |
5 ms |
42084 KB |
Output is correct |
15 |
Correct |
5 ms |
42076 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42076 KB |
Output is correct |
18 |
Correct |
7 ms |
42588 KB |
Output is correct |
19 |
Correct |
7 ms |
42708 KB |
Output is correct |
20 |
Correct |
7 ms |
42588 KB |
Output is correct |
21 |
Correct |
8 ms |
42588 KB |
Output is correct |
22 |
Correct |
7 ms |
42428 KB |
Output is correct |
23 |
Correct |
7 ms |
42588 KB |
Output is correct |
24 |
Correct |
7 ms |
42588 KB |
Output is correct |
25 |
Correct |
106 ms |
69820 KB |
Output is correct |
26 |
Correct |
93 ms |
70852 KB |
Output is correct |
27 |
Correct |
93 ms |
69952 KB |
Output is correct |
28 |
Correct |
147 ms |
66760 KB |
Output is correct |
29 |
Correct |
125 ms |
69248 KB |
Output is correct |
30 |
Correct |
124 ms |
67932 KB |
Output is correct |
31 |
Correct |
138 ms |
68544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
42076 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
232 ms |
59348 KB |
Output is correct |
4 |
Correct |
271 ms |
59708 KB |
Output is correct |
5 |
Correct |
241 ms |
58812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
42072 KB |
Output is correct |
2 |
Correct |
5 ms |
42076 KB |
Output is correct |
3 |
Correct |
5 ms |
42076 KB |
Output is correct |
4 |
Correct |
5 ms |
42072 KB |
Output is correct |
5 |
Correct |
5 ms |
42076 KB |
Output is correct |
6 |
Correct |
5 ms |
42052 KB |
Output is correct |
7 |
Correct |
5 ms |
42076 KB |
Output is correct |
8 |
Correct |
5 ms |
42052 KB |
Output is correct |
9 |
Correct |
5 ms |
42076 KB |
Output is correct |
10 |
Correct |
5 ms |
42076 KB |
Output is correct |
11 |
Correct |
5 ms |
42076 KB |
Output is correct |
12 |
Correct |
5 ms |
42076 KB |
Output is correct |
13 |
Correct |
5 ms |
42076 KB |
Output is correct |
14 |
Correct |
5 ms |
42084 KB |
Output is correct |
15 |
Correct |
5 ms |
42076 KB |
Output is correct |
16 |
Correct |
6 ms |
42076 KB |
Output is correct |
17 |
Correct |
6 ms |
42076 KB |
Output is correct |
18 |
Correct |
7 ms |
42588 KB |
Output is correct |
19 |
Correct |
7 ms |
42708 KB |
Output is correct |
20 |
Correct |
7 ms |
42588 KB |
Output is correct |
21 |
Correct |
8 ms |
42588 KB |
Output is correct |
22 |
Correct |
7 ms |
42428 KB |
Output is correct |
23 |
Correct |
7 ms |
42588 KB |
Output is correct |
24 |
Correct |
7 ms |
42588 KB |
Output is correct |
25 |
Correct |
5 ms |
42076 KB |
Output is correct |
26 |
Correct |
7 ms |
42668 KB |
Output is correct |
27 |
Correct |
8 ms |
42584 KB |
Output is correct |
28 |
Correct |
8 ms |
42588 KB |
Output is correct |
29 |
Correct |
7 ms |
42588 KB |
Output is correct |
30 |
Correct |
8 ms |
42292 KB |
Output is correct |
31 |
Correct |
8 ms |
42332 KB |
Output is correct |
32 |
Correct |
9 ms |
42452 KB |
Output is correct |
33 |
Correct |
8 ms |
42328 KB |
Output is correct |
34 |
Correct |
106 ms |
69820 KB |
Output is correct |
35 |
Correct |
93 ms |
70852 KB |
Output is correct |
36 |
Correct |
93 ms |
69952 KB |
Output is correct |
37 |
Correct |
147 ms |
66760 KB |
Output is correct |
38 |
Correct |
125 ms |
69248 KB |
Output is correct |
39 |
Correct |
124 ms |
67932 KB |
Output is correct |
40 |
Correct |
138 ms |
68544 KB |
Output is correct |
41 |
Correct |
5 ms |
42076 KB |
Output is correct |
42 |
Correct |
5 ms |
42076 KB |
Output is correct |
43 |
Correct |
232 ms |
59348 KB |
Output is correct |
44 |
Correct |
271 ms |
59708 KB |
Output is correct |
45 |
Correct |
241 ms |
58812 KB |
Output is correct |
46 |
Correct |
226 ms |
66692 KB |
Output is correct |
47 |
Correct |
191 ms |
66500 KB |
Output is correct |
48 |
Correct |
197 ms |
67760 KB |
Output is correct |
49 |
Correct |
199 ms |
67496 KB |
Output is correct |
50 |
Correct |
279 ms |
58276 KB |
Output is correct |
51 |
Correct |
325 ms |
59056 KB |
Output is correct |
52 |
Correct |
275 ms |
58300 KB |
Output is correct |
53 |
Correct |
301 ms |
58300 KB |
Output is correct |