#include<bits/stdc++.h>
using namespace std;
const int L = 18;
struct node {
vector<node*> l; // neighbors in the original graph
vector<node*> c; // children in the CT
int a, id; // a is the value of the node, id is its index
bool v = false; // initially, no node is marked
node* anc[L];
};
// <DSU>
int f(int i, int r[]){ // find representant of i
if(r[i] == i) return i;
return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
a = f(a, r);
b = f(b, r);
if(a == b) return;
if(s[a] > s[b]){
r[b] = a;
s[a] += s[b];
} else {
r[a] = b;
s[b] += s[a];
}
}
// </DSU>
int dist(node* u, node* v){
if(u->a < v->a) swap(u, v);
int d = u->a-v->a;
for(int i = 0;i < L;i++) if(d&(1<<i)) u = u->anc[i];
if(u == v) return d;
for(int i = L-1;i >= 0;i--){
if(u->anc[i] != v->anc[i]){
u = u->anc[i];
v = v->anc[i];
d += 2<<i;
}
}
return d+2;
}
long long dfs(node* n){
long long r = 0;
for(node* c : n->c) r = max(r, dfs(c)+dist(n, c));
return r;
}
void se(node* n, node* p, int d){
n->anc[0] = p;
n->a = d;
for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1];
for(node* c : n->l) if(c!=p) se(c, n, d+1);
}
void solve(){
// <boring setup>
int n,u,v;
cin >> n;
int m = n-1;
node g[n+1];
int o[n], r[n+1], s[n+1];
node* c[n+1]; // c[u] is the node with maximum value that u is connected to in the DSU, if u is its own representant
for(int i = 1;i <= n;i++) {
cin >> g[i].a;
g[i].id = i;
r[i] = i;
s[i] = 1;
c[i] = &g[i];
o[i-1] = i;
}
while(m--){
cin >> u >> v;
g[u].l.push_back(&g[v]);
g[v].l.push_back(&g[u]);
}
// </boring setup>
sort(o, o+n, [&g](int a, int b){return g[a].a < g[b].a;}); // sorting the nodes by value
for(int j = 0;j < n;j++){
node* d = &g[o[j]]; // d is the current node
d->v = true; // mark the current node
for(node* x : d->l){ // iterate over the neighbors of d
if(!x->v || f(x->id, r) == f(d->id, r)) continue; // x is unmarked or it's already connected to d
d->c.push_back(c[f(x->id, r)]); // add and edge in the CT between d and the node with maximum value that is connected to x
merge(x->id, d->id, r, s); // connect d and x in the DSU
c[f(d->id, r)] = d;
}
}
// Use the CT
se(&g[1], &g[1], 0);
cout << dfs(&g[o[n-1]]) << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1996 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1996 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
4 ms |
1924 KB |
Output is correct |
| 27 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 28 |
Correct |
4 ms |
2004 KB |
Output is correct |
| 29 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1748 KB |
Output is correct |
| 31 |
Correct |
3 ms |
1748 KB |
Output is correct |
| 32 |
Correct |
3 ms |
1744 KB |
Output is correct |
| 33 |
Correct |
3 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1996 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 25 |
Correct |
177 ms |
69648 KB |
Output is correct |
| 26 |
Correct |
166 ms |
69072 KB |
Output is correct |
| 27 |
Correct |
156 ms |
68976 KB |
Output is correct |
| 28 |
Correct |
223 ms |
67476 KB |
Output is correct |
| 29 |
Correct |
207 ms |
67564 KB |
Output is correct |
| 30 |
Correct |
204 ms |
67452 KB |
Output is correct |
| 31 |
Correct |
200 ms |
67476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
238 ms |
60576 KB |
Output is correct |
| 4 |
Correct |
231 ms |
60660 KB |
Output is correct |
| 5 |
Correct |
231 ms |
60540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
316 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 19 |
Correct |
3 ms |
1996 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2016 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 22 |
Correct |
4 ms |
1856 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2004 KB |
Output is correct |
| 24 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 25 |
Correct |
1 ms |
212 KB |
Output is correct |
| 26 |
Correct |
4 ms |
1924 KB |
Output is correct |
| 27 |
Correct |
4 ms |
1868 KB |
Output is correct |
| 28 |
Correct |
4 ms |
2004 KB |
Output is correct |
| 29 |
Correct |
3 ms |
1876 KB |
Output is correct |
| 30 |
Correct |
4 ms |
1748 KB |
Output is correct |
| 31 |
Correct |
3 ms |
1748 KB |
Output is correct |
| 32 |
Correct |
3 ms |
1744 KB |
Output is correct |
| 33 |
Correct |
3 ms |
1748 KB |
Output is correct |
| 34 |
Correct |
177 ms |
69648 KB |
Output is correct |
| 35 |
Correct |
166 ms |
69072 KB |
Output is correct |
| 36 |
Correct |
156 ms |
68976 KB |
Output is correct |
| 37 |
Correct |
223 ms |
67476 KB |
Output is correct |
| 38 |
Correct |
207 ms |
67564 KB |
Output is correct |
| 39 |
Correct |
204 ms |
67452 KB |
Output is correct |
| 40 |
Correct |
200 ms |
67476 KB |
Output is correct |
| 41 |
Correct |
0 ms |
212 KB |
Output is correct |
| 42 |
Correct |
1 ms |
340 KB |
Output is correct |
| 43 |
Correct |
238 ms |
60576 KB |
Output is correct |
| 44 |
Correct |
231 ms |
60660 KB |
Output is correct |
| 45 |
Correct |
231 ms |
60540 KB |
Output is correct |
| 46 |
Correct |
333 ms |
66412 KB |
Output is correct |
| 47 |
Correct |
326 ms |
66428 KB |
Output is correct |
| 48 |
Correct |
320 ms |
66380 KB |
Output is correct |
| 49 |
Correct |
345 ms |
66436 KB |
Output is correct |
| 50 |
Correct |
341 ms |
59384 KB |
Output is correct |
| 51 |
Correct |
313 ms |
59384 KB |
Output is correct |
| 52 |
Correct |
329 ms |
59360 KB |
Output is correct |
| 53 |
Correct |
320 ms |
59404 KB |
Output is correct |
