#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> adj;
int n;
const int LOG=63;
vector<int> p;
vector<int> depth;
vector<bool> proc;
vector<bool> visited;
vector<int> parent;
vector<vector<pair<int,int>>> child;
vector<vector<int>> ancestors;
vector<int> sz;
int lca(int a, int b){
if(depth[b]>depth[a]) swap(a,b);
int k=depth[a]-depth[b];
for (int j = LOG-1; j >= 0; j--)
{
if(k&((long long)1<<j)) a=ancestors[a][j];
}
if(a==b) return a;
for (int j = LOG-1; j >= 0; j--)
{
if(ancestors[a][j]!=ancestors[b][j]) {
a=ancestors[a][j];
b=ancestors[b][j];
}
}
return ancestors[a][0];
}
void setup_ancestors(){
for (int k = 1; k < LOG; k++)
{
for (int i = 0; i < n; i++)
{
ancestors[i][k]=ancestors[ancestors[i][k-1]][k-1];
}
}
}
int getParent(int a) {
if(a==parent[a]) return a;
return parent[a]=getParent(parent[a]);
}
void unify(int a, int b){
a=getParent(a);
b=getParent(b);
if(a==b) return;
int lc=lca(a,b);
int dist=(depth[a]+depth[b])-(2*depth[lc]);
parent[b]=a;
child[a].push_back({b,dist});
sz[a]+=sz[b];
}
void reconstructTree(){
vector<pair<int,int>> _p;
for (int i = 0; i < n; i++) _p.push_back({p[i], i});
sort(_p.begin(), _p.end());
for (int i = 0; i < n; i++)
{
for (auto u : adj[_p[i].second])
{
if(proc[u]) unify(_p[i].second, getParent(u));
}
proc[_p[i].second]=true;
}
}
void smltree(int i, int dpth){
if(visited[i]) return;
visited[i]=true;
depth[i]=dpth;
for (auto u : adj[i]) {
if(visited[u]) continue;
ancestors[u][0]=i;
smltree(u, depth[i]+1);
}
}
int dfs(int i){
int sum=0;
if(visited[i]) return 0;
visited[i]=true;
if(child[i].size()==0) return 0;
for (auto u : child[i]) {
sum=max(sum, dfs(u.first)+u.second);
}
return sum;
}
signed main() {
// Input:
cin >> n;
p.resize(n);
visited.resize(n, false);
parent.resize(n);
child.resize(n);
proc.resize(n);
depth.resize(n);
sz.resize(n, 1);
adj.resize(n);
int start;
for (int i = 0; i < n; i++){
cin >> p[i];
if (p[i] == n) start = i;
parent[i]=i;
}
for (int i = 0; i < n-1; i++)
{
int a,b; cin >> a >> b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
ancestors.resize(n, vector<int>(LOG, start));
smltree(start,0);
setup_ancestors();
reconstructTree();
visited.clear();
visited.resize(n, false);
cout << dfs(start) << "\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:131:22: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | cout << dfs(start) << "\n";
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
7 ms |
3932 KB |
Output is correct |
19 |
Correct |
7 ms |
3928 KB |
Output is correct |
20 |
Correct |
7 ms |
3928 KB |
Output is correct |
21 |
Correct |
7 ms |
3928 KB |
Output is correct |
22 |
Correct |
9 ms |
3944 KB |
Output is correct |
23 |
Correct |
8 ms |
3932 KB |
Output is correct |
24 |
Correct |
7 ms |
3936 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
7 ms |
3932 KB |
Output is correct |
19 |
Correct |
7 ms |
3928 KB |
Output is correct |
20 |
Correct |
7 ms |
3928 KB |
Output is correct |
21 |
Correct |
7 ms |
3928 KB |
Output is correct |
22 |
Correct |
9 ms |
3944 KB |
Output is correct |
23 |
Correct |
8 ms |
3932 KB |
Output is correct |
24 |
Correct |
7 ms |
3936 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
8 ms |
3932 KB |
Output is correct |
27 |
Correct |
12 ms |
3928 KB |
Output is correct |
28 |
Correct |
9 ms |
4024 KB |
Output is correct |
29 |
Correct |
8 ms |
3932 KB |
Output is correct |
30 |
Correct |
8 ms |
3852 KB |
Output is correct |
31 |
Correct |
9 ms |
3928 KB |
Output is correct |
32 |
Correct |
9 ms |
3932 KB |
Output is correct |
33 |
Correct |
8 ms |
3852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
7 ms |
3932 KB |
Output is correct |
19 |
Correct |
7 ms |
3928 KB |
Output is correct |
20 |
Correct |
7 ms |
3928 KB |
Output is correct |
21 |
Correct |
7 ms |
3928 KB |
Output is correct |
22 |
Correct |
9 ms |
3944 KB |
Output is correct |
23 |
Correct |
8 ms |
3932 KB |
Output is correct |
24 |
Correct |
7 ms |
3936 KB |
Output is correct |
25 |
Correct |
582 ms |
148176 KB |
Output is correct |
26 |
Correct |
571 ms |
147772 KB |
Output is correct |
27 |
Correct |
564 ms |
147780 KB |
Output is correct |
28 |
Correct |
624 ms |
144572 KB |
Output is correct |
29 |
Correct |
619 ms |
145960 KB |
Output is correct |
30 |
Correct |
625 ms |
145608 KB |
Output is correct |
31 |
Correct |
608 ms |
146080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
664 ms |
139392 KB |
Output is correct |
4 |
Correct |
664 ms |
139284 KB |
Output is correct |
5 |
Correct |
670 ms |
139520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
436 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
500 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
7 ms |
3932 KB |
Output is correct |
19 |
Correct |
7 ms |
3928 KB |
Output is correct |
20 |
Correct |
7 ms |
3928 KB |
Output is correct |
21 |
Correct |
7 ms |
3928 KB |
Output is correct |
22 |
Correct |
9 ms |
3944 KB |
Output is correct |
23 |
Correct |
8 ms |
3932 KB |
Output is correct |
24 |
Correct |
7 ms |
3936 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
8 ms |
3932 KB |
Output is correct |
27 |
Correct |
12 ms |
3928 KB |
Output is correct |
28 |
Correct |
9 ms |
4024 KB |
Output is correct |
29 |
Correct |
8 ms |
3932 KB |
Output is correct |
30 |
Correct |
8 ms |
3852 KB |
Output is correct |
31 |
Correct |
9 ms |
3928 KB |
Output is correct |
32 |
Correct |
9 ms |
3932 KB |
Output is correct |
33 |
Correct |
8 ms |
3852 KB |
Output is correct |
34 |
Correct |
582 ms |
148176 KB |
Output is correct |
35 |
Correct |
571 ms |
147772 KB |
Output is correct |
36 |
Correct |
564 ms |
147780 KB |
Output is correct |
37 |
Correct |
624 ms |
144572 KB |
Output is correct |
38 |
Correct |
619 ms |
145960 KB |
Output is correct |
39 |
Correct |
625 ms |
145608 KB |
Output is correct |
40 |
Correct |
608 ms |
146080 KB |
Output is correct |
41 |
Correct |
0 ms |
348 KB |
Output is correct |
42 |
Correct |
1 ms |
344 KB |
Output is correct |
43 |
Correct |
664 ms |
139392 KB |
Output is correct |
44 |
Correct |
664 ms |
139284 KB |
Output is correct |
45 |
Correct |
670 ms |
139520 KB |
Output is correct |
46 |
Correct |
722 ms |
146112 KB |
Output is correct |
47 |
Correct |
804 ms |
146040 KB |
Output is correct |
48 |
Correct |
791 ms |
146140 KB |
Output is correct |
49 |
Correct |
740 ms |
145416 KB |
Output is correct |
50 |
Correct |
801 ms |
139300 KB |
Output is correct |
51 |
Correct |
765 ms |
139480 KB |
Output is correct |
52 |
Correct |
753 ms |
138628 KB |
Output is correct |
53 |
Correct |
800 ms |
139356 KB |
Output is correct |