#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<int> parent;
vector<bool> already;
vector<vector<int>> adj;
vector<int> vaut;
vector<vector<int>> adjbase;
vector<int> depth;
vector<vector<int>> up;
//LCA
int get_lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int k=depth[a]-depth[b];
for (int j=19; j>=0; j--) {
if (k & (1<<j)) {
a=up[a][j];
}
}
if (a==b) return a;
for (int j=19; j>=0; j--) {
if (up[a][j]!=up[b][j]) {
a=up[a][j];
b=up[b][j];
}
}
return up[a][0];
}
//UNION FIND
int getparent(int x) {
if (x==parent[x]) return x;
return parent[x]=getparent(parent[x]);
}
bool same(int a, int b) {
return (getparent(a)==getparent(b));
}
void unite(int a, int b) {
if (!already[a]) return;
a=getparent(a);
b=getparent(b);
parent[a]=b;
adj[b].push_back(a);
}
//INIT
void initdfs(int s, int last=-1) {
for (auto u: adjbase[s]) {
if (u==last) continue;
depth[u] = depth[s]+1;
up[u][0]=s;
for (int i=1; i<20; i++) {
up[u][i]=up[ up[u][i-1] ][i-1];
}
initdfs(u, s);
}
}
//ANS CALCULATION
int calcans(int s) {
int ans=0;
for (auto u: adj[s]) {
int add=depth[u]+depth[s]-2LL*depth[get_lca(u, s)];
ans=max(ans, calcans(u)+add);
}
return ans;
}
void solve() {
cin >> n;
adj.resize(n+1);
already.resize(n+1, false);
adjbase.resize(n+1);
vaut.resize(n+1);
parent.resize(n+1);
depth.resize(n+1);
up.resize(n+1, vector<int>(20));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i=0; i<n; i++) {
parent[i]=i;
}
for (int i=0; i<n; i++) {
int u; cin >> u;
pq.push({u, i});
}
for (int i=0; i<n-1; i++) {
int u, v; cin >> u >> v;
u--, v--;
adjbase[u].push_back(v);
adjbase[v].push_back(u);
}
initdfs(0);
int last=0;
while (!pq.empty()) {
int s=pq.top().second; pq.pop();
last=s;
for (auto u: adjbase[s]) {
unite(u, s);
}
already[s]=true;
}
cout << calcans(last) << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
19 |
Correct |
6 ms |
2512 KB |
Output is correct |
20 |
Correct |
4 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
4 ms |
2396 KB |
Output is correct |
24 |
Correct |
4 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
19 |
Correct |
6 ms |
2512 KB |
Output is correct |
20 |
Correct |
4 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
4 ms |
2396 KB |
Output is correct |
24 |
Correct |
4 ms |
2396 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
5 ms |
2340 KB |
Output is correct |
27 |
Correct |
5 ms |
2396 KB |
Output is correct |
28 |
Correct |
5 ms |
2492 KB |
Output is correct |
29 |
Correct |
5 ms |
2396 KB |
Output is correct |
30 |
Correct |
4 ms |
2140 KB |
Output is correct |
31 |
Correct |
5 ms |
2140 KB |
Output is correct |
32 |
Correct |
6 ms |
2240 KB |
Output is correct |
33 |
Correct |
5 ms |
2140 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
19 |
Correct |
6 ms |
2512 KB |
Output is correct |
20 |
Correct |
4 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
4 ms |
2396 KB |
Output is correct |
24 |
Correct |
4 ms |
2396 KB |
Output is correct |
25 |
Correct |
229 ms |
88792 KB |
Output is correct |
26 |
Correct |
218 ms |
86716 KB |
Output is correct |
27 |
Correct |
226 ms |
86600 KB |
Output is correct |
28 |
Correct |
305 ms |
80684 KB |
Output is correct |
29 |
Correct |
261 ms |
81256 KB |
Output is correct |
30 |
Correct |
276 ms |
80316 KB |
Output is correct |
31 |
Correct |
308 ms |
80404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
306 ms |
73840 KB |
Output is correct |
4 |
Correct |
297 ms |
74460 KB |
Output is correct |
5 |
Correct |
266 ms |
73748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
456 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
19 |
Correct |
6 ms |
2512 KB |
Output is correct |
20 |
Correct |
4 ms |
2396 KB |
Output is correct |
21 |
Correct |
5 ms |
2396 KB |
Output is correct |
22 |
Correct |
4 ms |
2396 KB |
Output is correct |
23 |
Correct |
4 ms |
2396 KB |
Output is correct |
24 |
Correct |
4 ms |
2396 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
5 ms |
2340 KB |
Output is correct |
27 |
Correct |
5 ms |
2396 KB |
Output is correct |
28 |
Correct |
5 ms |
2492 KB |
Output is correct |
29 |
Correct |
5 ms |
2396 KB |
Output is correct |
30 |
Correct |
4 ms |
2140 KB |
Output is correct |
31 |
Correct |
5 ms |
2140 KB |
Output is correct |
32 |
Correct |
6 ms |
2240 KB |
Output is correct |
33 |
Correct |
5 ms |
2140 KB |
Output is correct |
34 |
Correct |
229 ms |
88792 KB |
Output is correct |
35 |
Correct |
218 ms |
86716 KB |
Output is correct |
36 |
Correct |
226 ms |
86600 KB |
Output is correct |
37 |
Correct |
305 ms |
80684 KB |
Output is correct |
38 |
Correct |
261 ms |
81256 KB |
Output is correct |
39 |
Correct |
276 ms |
80316 KB |
Output is correct |
40 |
Correct |
308 ms |
80404 KB |
Output is correct |
41 |
Correct |
1 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
306 ms |
73840 KB |
Output is correct |
44 |
Correct |
297 ms |
74460 KB |
Output is correct |
45 |
Correct |
266 ms |
73748 KB |
Output is correct |
46 |
Correct |
628 ms |
83604 KB |
Output is correct |
47 |
Correct |
592 ms |
83668 KB |
Output is correct |
48 |
Correct |
554 ms |
83644 KB |
Output is correct |
49 |
Correct |
575 ms |
84380 KB |
Output is correct |
50 |
Correct |
482 ms |
72288 KB |
Output is correct |
51 |
Correct |
502 ms |
72364 KB |
Output is correct |
52 |
Correct |
477 ms |
72412 KB |
Output is correct |
53 |
Correct |
481 ms |
72292 KB |
Output is correct |