#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 400005, INF = 2e9;
int n, a[MXN];
vector<int> edge[MXN];
int pos[MXN], p[MXN], C = 0;
pii fl[MXN];
vector<pii> edu[MXN];
bitset<MXN> ban;
struct SMG {
int val[MXN * 4], tag[MXN * 4];
void add_tag(int id, int t) {
val[id] += t;
tag[id] += t;
}
void push(int id) {
if (tag[id] == 0) return;
add_tag(id * 2 + 1, tag[id]);
add_tag(id * 2 + 2, tag[id]);
tag[id] = 0;
}
void pull(int id) {
val[id] = max(val[id * 2 + 1], val[id * 2 + 2]);
}
void init(int n) {
fill(val, val + 4 * n, 0);
fill(tag, tag + 4 * n, 0);
}
void modify(int id, int l, int r, int _l, int _r, int v) {
if (_r <= l || r <= _l) return;
if (_l <= l && r <= _r) {
add_tag(id, v);
return;
}
int mid = (l + r) >> 1;
push(id);
modify(id * 2 + 1, l, mid, _l, _r, v);
modify(id * 2 + 2, mid, r, _l, _r, v);
pull(id);
}
int query(int id, int l, int r, int _l, int _r) {
if (_r <= l || r <= _l) return INT_MIN;
if (_l <= l && r <= _r) return val[id];
int mid = (l + r) >> 1;
push(id);
return max(query(id * 2 + 1, l, mid, _l, _r), query(id * 2 + 2, mid, r, _l, _r));
}
void DFS(int id, int l, int r) {
if (l + 1 == r) {
cout << (val[id] <= 0 ? -1 : val[id]) << ' ';
return;
}
int mid = (l + r) >> 1;
push(id);
DFS(id * 2 + 1, l, mid);
DFS(id * 2 + 2, mid, r);
}
} smg;
namespace LEN {
vector<int> v;
SMG smg;
int pos[MXN], d[MXN], n;
void DFS(int id, int par, int dep) {
pos[id] = v.size();
d[id] = dep;
v.push_back(dep);
for (auto &i : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
v.push_back(dep);
}
}
void BUILD(int rt) {
DFS(rt, 0, 0);
n = v.size();
smg.init(n);
FOR(i, 0, n) smg.modify(0, 0, n, i, i + 1, -v[i]);
}
int calc(int l, int r) {
if (pos[l] > pos[r]) swap(l, r);
return d[l] + d[r] + 2 * smg.query(0, 0, n, pos[l], pos[r] + 1);
}
}
void FLAT(int id, int par) {
fl[id].fs = C++;
p[id] = par;
for (auto &i : edge[id]) {
if (i == par) continue;
FLAT(i, id);
}
fl[id].sc = C;
}
void BAN(int id) {
// debug("BAN", id, fl[id].fs, fl[id].sc);
smg.modify(0, 0, n, fl[id].fs, fl[id].sc, -INF);
}
void UNBAN(int id) {
smg.modify(0, 0, n, fl[id].fs, fl[id].sc, INF);
}
void EDU_PUSH(int x, int y, int l) {
edu[x].push_back(mp(l, y));
}
int solve(int id, int rt) {
// debug(id, rt);
// smg.DFS(0, 0, n);
// cout << endl;
if (id == 0) return 0;
int ct = smg.query(0, 0, n, fl[id].fs, fl[id].sc);
if (ct <= 0) return 0;
ct = pos[ct];
// debug(ct);
ban[ct] = true;
BAN(ct);
int pp = solve(rt, rt);
if (pp) EDU_PUSH(ct, pp, LEN::calc(ct, pp));
UNBAN(ct);
for (auto &i : edge[ct]) {
if (i == p[ct]) continue;
if (ban[i]) continue;
int pp = solve(i, i);
EDU_PUSH(ct, pp, LEN::calc(ct, pp));
}
return ct;
}
int eduroam(int id) {
int ans = 0;
for (auto &i : edu[id]) {
ans = max(ans, i.fs + eduroam(i.sc));
}
return ans;
}
void miku() {
int x, y;
cin >> n;
FOR(i, 1, n + 1) {
cin >> a[i];
pos[a[i]] = i;
}
FOR(i, 1, n) {
cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
LEN::BUILD(1);
// debug(LEN::calc(3, 5));
// LEN::calc(3, 5);
FLAT(1, 0);
smg.init(n);
FOR(i, 1, n + 1) smg.modify(0, 0, n, fl[i].fs, fl[i].fs + 1, a[i]);
int rt = solve(1, 1);
// FOR(i, 1, n + 1) {
// for (auto &j : edu[i]) cout << '<' << j.fs << ' ' << j.sc << "> ";
// cout << '\n';
// }
cout << eduroam(rt) << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
miku();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
11 |
Correct |
7 ms |
33372 KB |
Output is correct |
12 |
Correct |
6 ms |
33116 KB |
Output is correct |
13 |
Correct |
6 ms |
33116 KB |
Output is correct |
14 |
Correct |
8 ms |
33116 KB |
Output is correct |
15 |
Correct |
6 ms |
33116 KB |
Output is correct |
16 |
Correct |
6 ms |
33112 KB |
Output is correct |
17 |
Correct |
7 ms |
33116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
11 |
Correct |
7 ms |
33372 KB |
Output is correct |
12 |
Correct |
6 ms |
33116 KB |
Output is correct |
13 |
Correct |
6 ms |
33116 KB |
Output is correct |
14 |
Correct |
8 ms |
33116 KB |
Output is correct |
15 |
Correct |
6 ms |
33116 KB |
Output is correct |
16 |
Correct |
6 ms |
33112 KB |
Output is correct |
17 |
Correct |
7 ms |
33116 KB |
Output is correct |
18 |
Correct |
12 ms |
38488 KB |
Output is correct |
19 |
Correct |
13 ms |
38492 KB |
Output is correct |
20 |
Correct |
13 ms |
38492 KB |
Output is correct |
21 |
Correct |
12 ms |
37980 KB |
Output is correct |
22 |
Correct |
12 ms |
37980 KB |
Output is correct |
23 |
Correct |
12 ms |
38096 KB |
Output is correct |
24 |
Correct |
13 ms |
37976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
11 |
Correct |
7 ms |
33372 KB |
Output is correct |
12 |
Correct |
6 ms |
33116 KB |
Output is correct |
13 |
Correct |
6 ms |
33116 KB |
Output is correct |
14 |
Correct |
8 ms |
33116 KB |
Output is correct |
15 |
Correct |
6 ms |
33116 KB |
Output is correct |
16 |
Correct |
6 ms |
33112 KB |
Output is correct |
17 |
Correct |
7 ms |
33116 KB |
Output is correct |
18 |
Correct |
12 ms |
38488 KB |
Output is correct |
19 |
Correct |
13 ms |
38492 KB |
Output is correct |
20 |
Correct |
13 ms |
38492 KB |
Output is correct |
21 |
Correct |
12 ms |
37980 KB |
Output is correct |
22 |
Correct |
12 ms |
37980 KB |
Output is correct |
23 |
Correct |
12 ms |
38096 KB |
Output is correct |
24 |
Correct |
13 ms |
37976 KB |
Output is correct |
25 |
Correct |
6 ms |
33240 KB |
Output is correct |
26 |
Correct |
19 ms |
38232 KB |
Output is correct |
27 |
Correct |
16 ms |
38236 KB |
Output is correct |
28 |
Correct |
14 ms |
38232 KB |
Output is correct |
29 |
Correct |
14 ms |
38236 KB |
Output is correct |
30 |
Correct |
14 ms |
37984 KB |
Output is correct |
31 |
Correct |
13 ms |
37980 KB |
Output is correct |
32 |
Correct |
14 ms |
37980 KB |
Output is correct |
33 |
Correct |
14 ms |
37996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
11 |
Correct |
7 ms |
33372 KB |
Output is correct |
12 |
Correct |
6 ms |
33116 KB |
Output is correct |
13 |
Correct |
6 ms |
33116 KB |
Output is correct |
14 |
Correct |
8 ms |
33116 KB |
Output is correct |
15 |
Correct |
6 ms |
33116 KB |
Output is correct |
16 |
Correct |
6 ms |
33112 KB |
Output is correct |
17 |
Correct |
7 ms |
33116 KB |
Output is correct |
18 |
Correct |
12 ms |
38488 KB |
Output is correct |
19 |
Correct |
13 ms |
38492 KB |
Output is correct |
20 |
Correct |
13 ms |
38492 KB |
Output is correct |
21 |
Correct |
12 ms |
37980 KB |
Output is correct |
22 |
Correct |
12 ms |
37980 KB |
Output is correct |
23 |
Correct |
12 ms |
38096 KB |
Output is correct |
24 |
Correct |
13 ms |
37976 KB |
Output is correct |
25 |
Correct |
317 ms |
123780 KB |
Output is correct |
26 |
Correct |
331 ms |
121780 KB |
Output is correct |
27 |
Correct |
312 ms |
121052 KB |
Output is correct |
28 |
Correct |
307 ms |
107360 KB |
Output is correct |
29 |
Correct |
315 ms |
107820 KB |
Output is correct |
30 |
Correct |
304 ms |
107956 KB |
Output is correct |
31 |
Correct |
311 ms |
107624 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33116 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
375 ms |
98540 KB |
Output is correct |
4 |
Correct |
376 ms |
103312 KB |
Output is correct |
5 |
Correct |
368 ms |
102868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
33112 KB |
Output is correct |
2 |
Correct |
7 ms |
33116 KB |
Output is correct |
3 |
Correct |
6 ms |
33116 KB |
Output is correct |
4 |
Correct |
6 ms |
33116 KB |
Output is correct |
5 |
Correct |
6 ms |
33300 KB |
Output is correct |
6 |
Correct |
6 ms |
33116 KB |
Output is correct |
7 |
Correct |
6 ms |
33204 KB |
Output is correct |
8 |
Correct |
7 ms |
33116 KB |
Output is correct |
9 |
Correct |
6 ms |
33116 KB |
Output is correct |
10 |
Correct |
7 ms |
33116 KB |
Output is correct |
11 |
Correct |
7 ms |
33372 KB |
Output is correct |
12 |
Correct |
6 ms |
33116 KB |
Output is correct |
13 |
Correct |
6 ms |
33116 KB |
Output is correct |
14 |
Correct |
8 ms |
33116 KB |
Output is correct |
15 |
Correct |
6 ms |
33116 KB |
Output is correct |
16 |
Correct |
6 ms |
33112 KB |
Output is correct |
17 |
Correct |
7 ms |
33116 KB |
Output is correct |
18 |
Correct |
12 ms |
38488 KB |
Output is correct |
19 |
Correct |
13 ms |
38492 KB |
Output is correct |
20 |
Correct |
13 ms |
38492 KB |
Output is correct |
21 |
Correct |
12 ms |
37980 KB |
Output is correct |
22 |
Correct |
12 ms |
37980 KB |
Output is correct |
23 |
Correct |
12 ms |
38096 KB |
Output is correct |
24 |
Correct |
13 ms |
37976 KB |
Output is correct |
25 |
Correct |
6 ms |
33240 KB |
Output is correct |
26 |
Correct |
19 ms |
38232 KB |
Output is correct |
27 |
Correct |
16 ms |
38236 KB |
Output is correct |
28 |
Correct |
14 ms |
38232 KB |
Output is correct |
29 |
Correct |
14 ms |
38236 KB |
Output is correct |
30 |
Correct |
14 ms |
37984 KB |
Output is correct |
31 |
Correct |
13 ms |
37980 KB |
Output is correct |
32 |
Correct |
14 ms |
37980 KB |
Output is correct |
33 |
Correct |
14 ms |
37996 KB |
Output is correct |
34 |
Correct |
317 ms |
123780 KB |
Output is correct |
35 |
Correct |
331 ms |
121780 KB |
Output is correct |
36 |
Correct |
312 ms |
121052 KB |
Output is correct |
37 |
Correct |
307 ms |
107360 KB |
Output is correct |
38 |
Correct |
315 ms |
107820 KB |
Output is correct |
39 |
Correct |
304 ms |
107956 KB |
Output is correct |
40 |
Correct |
311 ms |
107624 KB |
Output is correct |
41 |
Correct |
6 ms |
33116 KB |
Output is correct |
42 |
Correct |
7 ms |
33116 KB |
Output is correct |
43 |
Correct |
375 ms |
98540 KB |
Output is correct |
44 |
Correct |
376 ms |
103312 KB |
Output is correct |
45 |
Correct |
368 ms |
102868 KB |
Output is correct |
46 |
Correct |
486 ms |
119240 KB |
Output is correct |
47 |
Correct |
512 ms |
119752 KB |
Output is correct |
48 |
Correct |
493 ms |
119488 KB |
Output is correct |
49 |
Correct |
495 ms |
119948 KB |
Output is correct |
50 |
Correct |
498 ms |
100028 KB |
Output is correct |
51 |
Correct |
473 ms |
100812 KB |
Output is correct |
52 |
Correct |
511 ms |
100704 KB |
Output is correct |
53 |
Correct |
465 ms |
100500 KB |
Output is correct |