#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,p[200005],pos[200005];
vector<int>g[200005];
int bl[20][200005];
int lg[200005];
int tt[200005],sz[200005];
int cine[200005];
int h[200005],t[200005];
int dp[200005];
void dfs(int nod,int tata)
{
for (auto vecin : g[nod])
{
if (vecin != tata)
{
h[vecin] = 1 + h[nod];
t[vecin] = nod;
dfs(vecin,nod);
}
}
}
int root(int x)
{
while (x != tt[x])
x = tt[x];
return x;
}
void unite(int x,int y)
{
x = root(x);
y = root(y);
if (x == y)
return;
if (sz[x] < sz[y])
swap(x,y);
tt[y] = x;
sz[x] += sz[y];
if (p[cine[y]] > p[cine[x]])
cine[x] = cine[y];
}
int lca(int x,int y)
{
if (h[x] > h[y])
swap(x,y);
for (int st = lg[n]; st >= 0; st--)
if (h[y] - (1 << st) >= h[x])
y = bl[st][y];
if (x == y)
return x;
for (int st = lg[n]; st >= 0; st--)
if (bl[st][x] != bl[st][y])
x = bl[st][x],y = bl[st][y];
return t[x];
}
int dist(int x,int y)
{
return h[x] + h[y] - 2 * h[lca(x,y)];
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i],pos[p[i]] = i;
for (int i = 1; i <= n; i++)
tt[i] = i,sz[i] = 1,cine[i] = i;
for (int i = 1; i < n; i++)
{
int x,y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
for (int i = 2; i <= n; i++)
lg[i] = 1 + lg[i / 2];
for (int i = 1; i <= n; i++)
bl[0][i] = t[i];
for (int j = 1; j <= lg[n]; j++)
for (int i = 1; i <= n; i++)
bl[j][i] = bl[j - 1][bl[j - 1][i]];
for (int i = 1; i <= n; i++)
{
int nod = pos[i];
for (auto vecin : g[nod])
{
if (p[vecin] < p[nod])
{
int x = cine[root(vecin)];
dp[nod] = max(dp[nod],dp[x] + dist(nod,x));
unite(nod,vecin);
}
}
}
cout << dp[pos[n]];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
11 |
Correct |
6 ms |
29016 KB |
Output is correct |
12 |
Correct |
5 ms |
29016 KB |
Output is correct |
13 |
Correct |
5 ms |
29016 KB |
Output is correct |
14 |
Correct |
5 ms |
29020 KB |
Output is correct |
15 |
Correct |
5 ms |
29016 KB |
Output is correct |
16 |
Correct |
5 ms |
29020 KB |
Output is correct |
17 |
Correct |
5 ms |
29016 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
11 |
Correct |
6 ms |
29016 KB |
Output is correct |
12 |
Correct |
5 ms |
29016 KB |
Output is correct |
13 |
Correct |
5 ms |
29016 KB |
Output is correct |
14 |
Correct |
5 ms |
29020 KB |
Output is correct |
15 |
Correct |
5 ms |
29016 KB |
Output is correct |
16 |
Correct |
5 ms |
29020 KB |
Output is correct |
17 |
Correct |
5 ms |
29016 KB |
Output is correct |
18 |
Correct |
10 ms |
35936 KB |
Output is correct |
19 |
Correct |
7 ms |
35932 KB |
Output is correct |
20 |
Correct |
8 ms |
35928 KB |
Output is correct |
21 |
Correct |
8 ms |
35932 KB |
Output is correct |
22 |
Correct |
7 ms |
35928 KB |
Output is correct |
23 |
Correct |
7 ms |
35932 KB |
Output is correct |
24 |
Correct |
7 ms |
35928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
11 |
Correct |
6 ms |
29016 KB |
Output is correct |
12 |
Correct |
5 ms |
29016 KB |
Output is correct |
13 |
Correct |
5 ms |
29016 KB |
Output is correct |
14 |
Correct |
5 ms |
29020 KB |
Output is correct |
15 |
Correct |
5 ms |
29016 KB |
Output is correct |
16 |
Correct |
5 ms |
29020 KB |
Output is correct |
17 |
Correct |
5 ms |
29016 KB |
Output is correct |
18 |
Correct |
10 ms |
35936 KB |
Output is correct |
19 |
Correct |
7 ms |
35932 KB |
Output is correct |
20 |
Correct |
8 ms |
35928 KB |
Output is correct |
21 |
Correct |
8 ms |
35932 KB |
Output is correct |
22 |
Correct |
7 ms |
35928 KB |
Output is correct |
23 |
Correct |
7 ms |
35932 KB |
Output is correct |
24 |
Correct |
7 ms |
35928 KB |
Output is correct |
25 |
Correct |
3 ms |
18776 KB |
Output is correct |
26 |
Correct |
8 ms |
35672 KB |
Output is correct |
27 |
Correct |
9 ms |
35932 KB |
Output is correct |
28 |
Correct |
8 ms |
35672 KB |
Output is correct |
29 |
Correct |
7 ms |
35672 KB |
Output is correct |
30 |
Correct |
8 ms |
35416 KB |
Output is correct |
31 |
Correct |
8 ms |
35420 KB |
Output is correct |
32 |
Correct |
8 ms |
35416 KB |
Output is correct |
33 |
Correct |
9 ms |
35416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
11 |
Correct |
6 ms |
29016 KB |
Output is correct |
12 |
Correct |
5 ms |
29016 KB |
Output is correct |
13 |
Correct |
5 ms |
29016 KB |
Output is correct |
14 |
Correct |
5 ms |
29020 KB |
Output is correct |
15 |
Correct |
5 ms |
29016 KB |
Output is correct |
16 |
Correct |
5 ms |
29020 KB |
Output is correct |
17 |
Correct |
5 ms |
29016 KB |
Output is correct |
18 |
Correct |
10 ms |
35936 KB |
Output is correct |
19 |
Correct |
7 ms |
35932 KB |
Output is correct |
20 |
Correct |
8 ms |
35928 KB |
Output is correct |
21 |
Correct |
8 ms |
35932 KB |
Output is correct |
22 |
Correct |
7 ms |
35928 KB |
Output is correct |
23 |
Correct |
7 ms |
35932 KB |
Output is correct |
24 |
Correct |
7 ms |
35928 KB |
Output is correct |
25 |
Correct |
92 ms |
67412 KB |
Output is correct |
26 |
Correct |
95 ms |
70948 KB |
Output is correct |
27 |
Correct |
90 ms |
70992 KB |
Output is correct |
28 |
Correct |
163 ms |
70976 KB |
Output is correct |
29 |
Correct |
165 ms |
70996 KB |
Output is correct |
30 |
Correct |
149 ms |
70992 KB |
Output is correct |
31 |
Correct |
163 ms |
70968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
5 ms |
26968 KB |
Output is correct |
3 |
Correct |
300 ms |
56524 KB |
Output is correct |
4 |
Correct |
293 ms |
56144 KB |
Output is correct |
5 |
Correct |
269 ms |
56144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
18776 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20824 KB |
Output is correct |
4 |
Correct |
4 ms |
22872 KB |
Output is correct |
5 |
Correct |
4 ms |
22872 KB |
Output is correct |
6 |
Correct |
5 ms |
22872 KB |
Output is correct |
7 |
Correct |
4 ms |
18776 KB |
Output is correct |
8 |
Correct |
4 ms |
22876 KB |
Output is correct |
9 |
Correct |
5 ms |
22872 KB |
Output is correct |
10 |
Correct |
4 ms |
22872 KB |
Output is correct |
11 |
Correct |
6 ms |
29016 KB |
Output is correct |
12 |
Correct |
5 ms |
29016 KB |
Output is correct |
13 |
Correct |
5 ms |
29016 KB |
Output is correct |
14 |
Correct |
5 ms |
29020 KB |
Output is correct |
15 |
Correct |
5 ms |
29016 KB |
Output is correct |
16 |
Correct |
5 ms |
29020 KB |
Output is correct |
17 |
Correct |
5 ms |
29016 KB |
Output is correct |
18 |
Correct |
10 ms |
35936 KB |
Output is correct |
19 |
Correct |
7 ms |
35932 KB |
Output is correct |
20 |
Correct |
8 ms |
35928 KB |
Output is correct |
21 |
Correct |
8 ms |
35932 KB |
Output is correct |
22 |
Correct |
7 ms |
35928 KB |
Output is correct |
23 |
Correct |
7 ms |
35932 KB |
Output is correct |
24 |
Correct |
7 ms |
35928 KB |
Output is correct |
25 |
Correct |
3 ms |
18776 KB |
Output is correct |
26 |
Correct |
8 ms |
35672 KB |
Output is correct |
27 |
Correct |
9 ms |
35932 KB |
Output is correct |
28 |
Correct |
8 ms |
35672 KB |
Output is correct |
29 |
Correct |
7 ms |
35672 KB |
Output is correct |
30 |
Correct |
8 ms |
35416 KB |
Output is correct |
31 |
Correct |
8 ms |
35420 KB |
Output is correct |
32 |
Correct |
8 ms |
35416 KB |
Output is correct |
33 |
Correct |
9 ms |
35416 KB |
Output is correct |
34 |
Correct |
92 ms |
67412 KB |
Output is correct |
35 |
Correct |
95 ms |
70948 KB |
Output is correct |
36 |
Correct |
90 ms |
70992 KB |
Output is correct |
37 |
Correct |
163 ms |
70976 KB |
Output is correct |
38 |
Correct |
165 ms |
70996 KB |
Output is correct |
39 |
Correct |
149 ms |
70992 KB |
Output is correct |
40 |
Correct |
163 ms |
70968 KB |
Output is correct |
41 |
Correct |
4 ms |
18776 KB |
Output is correct |
42 |
Correct |
5 ms |
26968 KB |
Output is correct |
43 |
Correct |
300 ms |
56524 KB |
Output is correct |
44 |
Correct |
293 ms |
56144 KB |
Output is correct |
45 |
Correct |
269 ms |
56144 KB |
Output is correct |
46 |
Correct |
315 ms |
65924 KB |
Output is correct |
47 |
Correct |
278 ms |
64592 KB |
Output is correct |
48 |
Correct |
281 ms |
66372 KB |
Output is correct |
49 |
Correct |
327 ms |
64848 KB |
Output is correct |
50 |
Correct |
381 ms |
59472 KB |
Output is correct |
51 |
Correct |
374 ms |
59568 KB |
Output is correct |
52 |
Correct |
374 ms |
59592 KB |
Output is correct |
53 |
Correct |
350 ms |
59472 KB |
Output is correct |