#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int max_log = 18;
const int inf = 1000000000;
int n;
vector<int> g[maxn];
int depth[maxn];
long long dp[maxn];
int permutation[maxn];
int jump[maxn][max_log];
void dfs(int node, int par, int dep)
{
depth[node] = 1 + depth[par];
for (auto next_node : g[node])
{
if (next_node != par)
{
jump[next_node][0] = node;
dfs(next_node, node, dep + 1);
}
}
}
void build_sparse()
{
for (int i = 0; i <= max_log - 1; ++i)
{
jump[1][i] = 1;
}
for (int i = 1; i <= max_log - 1; ++i)
{
for (int j = 1; j <= n; ++j)
{
jump[j][i] = jump[jump[j][i - 1]][i - 1];
}
}
}
int find_lca(int x, int y)
{
if (depth[x] < depth[y])
{
swap(x, y);
}
int diff = depth[x] - depth[y];
for (int i = 0; i <= max_log - 1; ++i)
{
if ((diff & (1 << i)) != 0)
{
x = jump[x][i];
diff -= (1 << i);
if (diff == 0)
{
break;
}
}
}
if (x == y)
{
return x;
}
for (int i = max_log - 1; i >= 0; --i)
{
if (jump[x][i] != jump[y][i])
{
x = jump[x][i];
y = jump[y][i];
}
}
return jump[x][0];
}
int find_dist(int x, int y)
{
return depth[x] + depth[y] - 2 * depth[find_lca(x, y)];
}
int parent[maxn];
int dsu_rank[maxn];
int component_current_root[maxn];
int find_root(int node)
{
if (parent[node] == node)
{
return node;
}
return parent[node] = find_root(parent[node]);
}
void connect(int x, int y)
{
x = find_root(x);
y = find_root(y);
if (x == y)
{
return;
}
if (dsu_rank[x] < dsu_rank[y])
{
swap(x, y);
}
if (dsu_rank[x] == dsu_rank[y])
{
++dsu_rank[y];
}
parent[x] = y;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> permutation[i];
}
for (int i = 1; i <= n - 1; ++i)
{
int x, y;
cin >> x >> y;
x = permutation[x];
y = permutation[y];
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, -1, 0);
build_sparse();
/*for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
cout << i << ' ' << j << ' ' << find_lca(i, j) << endl;
}
}*/
for (int i = 1; i <= n; ++i)
{
dsu_rank[i] = 1;
parent[i] = i;
component_current_root[i] = i;
}
for (int node = 1; node <= n; ++node)
{
for (auto next_node : g[node])
{
if (next_node > node)
{
continue;
}
dp[node] = max(dp[node], dp[component_current_root[find_root(next_node)]] + find_dist(node, component_current_root[find_root(next_node)]));
connect(node, next_node);
}
component_current_root[find_root(node)] = node;
}
cout << dp[n] << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5020 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5020 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
5076 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5972 KB |
Output is correct |
20 |
Correct |
4 ms |
5972 KB |
Output is correct |
21 |
Correct |
4 ms |
5876 KB |
Output is correct |
22 |
Correct |
4 ms |
6056 KB |
Output is correct |
23 |
Correct |
4 ms |
5844 KB |
Output is correct |
24 |
Correct |
5 ms |
5972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5020 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
5076 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5972 KB |
Output is correct |
20 |
Correct |
4 ms |
5972 KB |
Output is correct |
21 |
Correct |
4 ms |
5876 KB |
Output is correct |
22 |
Correct |
4 ms |
6056 KB |
Output is correct |
23 |
Correct |
4 ms |
5844 KB |
Output is correct |
24 |
Correct |
5 ms |
5972 KB |
Output is correct |
25 |
Correct |
2 ms |
5028 KB |
Output is correct |
26 |
Correct |
5 ms |
5932 KB |
Output is correct |
27 |
Correct |
4 ms |
5932 KB |
Output is correct |
28 |
Correct |
4 ms |
5972 KB |
Output is correct |
29 |
Correct |
4 ms |
5928 KB |
Output is correct |
30 |
Correct |
4 ms |
5716 KB |
Output is correct |
31 |
Correct |
4 ms |
5716 KB |
Output is correct |
32 |
Correct |
5 ms |
5676 KB |
Output is correct |
33 |
Correct |
4 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5020 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
5076 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5972 KB |
Output is correct |
20 |
Correct |
4 ms |
5972 KB |
Output is correct |
21 |
Correct |
4 ms |
5876 KB |
Output is correct |
22 |
Correct |
4 ms |
6056 KB |
Output is correct |
23 |
Correct |
4 ms |
5844 KB |
Output is correct |
24 |
Correct |
5 ms |
5972 KB |
Output is correct |
25 |
Correct |
96 ms |
37828 KB |
Output is correct |
26 |
Correct |
93 ms |
46924 KB |
Output is correct |
27 |
Correct |
95 ms |
46904 KB |
Output is correct |
28 |
Correct |
139 ms |
46412 KB |
Output is correct |
29 |
Correct |
142 ms |
40940 KB |
Output is correct |
30 |
Correct |
132 ms |
44936 KB |
Output is correct |
31 |
Correct |
148 ms |
43700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
5076 KB |
Output is correct |
3 |
Correct |
135 ms |
31488 KB |
Output is correct |
4 |
Correct |
125 ms |
34428 KB |
Output is correct |
5 |
Correct |
139 ms |
34500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
5020 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
5020 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
13 |
Correct |
3 ms |
5080 KB |
Output is correct |
14 |
Correct |
3 ms |
5024 KB |
Output is correct |
15 |
Correct |
3 ms |
5076 KB |
Output is correct |
16 |
Correct |
3 ms |
5076 KB |
Output is correct |
17 |
Correct |
2 ms |
5076 KB |
Output is correct |
18 |
Correct |
4 ms |
5844 KB |
Output is correct |
19 |
Correct |
5 ms |
5972 KB |
Output is correct |
20 |
Correct |
4 ms |
5972 KB |
Output is correct |
21 |
Correct |
4 ms |
5876 KB |
Output is correct |
22 |
Correct |
4 ms |
6056 KB |
Output is correct |
23 |
Correct |
4 ms |
5844 KB |
Output is correct |
24 |
Correct |
5 ms |
5972 KB |
Output is correct |
25 |
Correct |
2 ms |
5028 KB |
Output is correct |
26 |
Correct |
5 ms |
5932 KB |
Output is correct |
27 |
Correct |
4 ms |
5932 KB |
Output is correct |
28 |
Correct |
4 ms |
5972 KB |
Output is correct |
29 |
Correct |
4 ms |
5928 KB |
Output is correct |
30 |
Correct |
4 ms |
5716 KB |
Output is correct |
31 |
Correct |
4 ms |
5716 KB |
Output is correct |
32 |
Correct |
5 ms |
5676 KB |
Output is correct |
33 |
Correct |
4 ms |
5716 KB |
Output is correct |
34 |
Correct |
96 ms |
37828 KB |
Output is correct |
35 |
Correct |
93 ms |
46924 KB |
Output is correct |
36 |
Correct |
95 ms |
46904 KB |
Output is correct |
37 |
Correct |
139 ms |
46412 KB |
Output is correct |
38 |
Correct |
142 ms |
40940 KB |
Output is correct |
39 |
Correct |
132 ms |
44936 KB |
Output is correct |
40 |
Correct |
148 ms |
43700 KB |
Output is correct |
41 |
Correct |
2 ms |
4948 KB |
Output is correct |
42 |
Correct |
2 ms |
5076 KB |
Output is correct |
43 |
Correct |
135 ms |
31488 KB |
Output is correct |
44 |
Correct |
125 ms |
34428 KB |
Output is correct |
45 |
Correct |
139 ms |
34500 KB |
Output is correct |
46 |
Correct |
105 ms |
43340 KB |
Output is correct |
47 |
Correct |
106 ms |
43252 KB |
Output is correct |
48 |
Correct |
107 ms |
43364 KB |
Output is correct |
49 |
Correct |
110 ms |
43252 KB |
Output is correct |
50 |
Correct |
150 ms |
34656 KB |
Output is correct |
51 |
Correct |
144 ms |
34636 KB |
Output is correct |
52 |
Correct |
151 ms |
34668 KB |
Output is correct |
53 |
Correct |
145 ms |
34704 KB |
Output is correct |