QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673811 | #2999. 春节十二响 | propane | 100 ✓ | 65ms | 41680kb | C++20 | 1.4kb | 2024-10-25 10:31:31 | 2024-10-25 10:31:31 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
vector<int> g[maxn];
int v[maxn], len[maxn];
multiset<int> s[maxn];
void dfs1(int u){
for(auto &j : g[u]){
dfs1(j);
len[u] = max(len[u], len[j] + 1);
if (len[j] > len[g[u][0]]) swap(j, g[u][0]);
}
}
void dfs2(int u){
if (g[u].empty()){
s[u].insert(v[u]);
return;
}
dfs2(g[u][0]);
s[u].swap(s[g[u][0]]);
for(int i = 1; i < g[u].size(); i++){
int j = g[u][i];
dfs2(j);
vector<int> p;
while(!s[j].empty()){
p.push_back(max(*prev(s[u].end()), *prev(s[j].end())));
s[u].erase(prev(s[u].end()));
s[j].erase(prev(s[j].end()));
}
for(auto x : p) s[u].insert(x);
}
s[u].insert(v[u]);
// cout << u << ":\n";
// for(auto x : s[u]) cout << x << ' ';
// cout << '\n';
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> v[i];
for(int i = 2; i <= n; i++){
int x;
cin >> x;
g[x].push_back(i);
}
dfs1(1);
dfs2(1);
LL ans = 0;
for(auto x : s[1]) ans += x;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 15464kb
input:
3 4 10 5 1 2
output:
19
result:
ok single line: '19'
Test #2:
score: 5
Accepted
time: 4ms
memory: 15672kb
input:
5 10 8 1 1 7 1 1 2 2
output:
25
result:
ok single line: '25'
Test #3:
score: 5
Accepted
time: 4ms
memory: 14944kb
input:
10 1 2 2 1 1 2 1 1 1 2 1 1 1 2 5 5 5 8 1
output:
7
result:
ok single line: '7'
Test #4:
score: 5
Accepted
time: 0ms
memory: 14376kb
input:
10 1 1 2 1 2 2 1 2 1 1 1 2 3 4 3 6 2 1 6
output:
7
result:
ok single line: '7'
Test #5:
score: 5
Accepted
time: 3ms
memory: 14240kb
input:
15 5 9 5 1 7 3 8 3 1 7 3 1 1 5 8 1 2 2 2 4 1 5 1 2 9 7 12 1 12
output:
25
result:
ok single line: '25'
Test #6:
score: 5
Accepted
time: 0ms
memory: 15252kb
input:
16 8 9 19 9 13 9 17 8 9 20 20 7 2 12 19 6 1 2 1 4 3 5 5 8 6 10 3 8 7 4 3
output:
85
result:
ok single line: '85'
Test #7:
score: 5
Accepted
time: 0ms
memory: 15780kb
input:
16 177269241 136479857 518040716 590690929 837228149 71462256 887232525 317436776 138552464 727415824 697621256 859965262 588521417 821100487 594324041 92665222 1 2 1 1 2 2 3 3 5 8 3 8 5 3 5
output:
2339518886
result:
ok single line: '2339518886'
Test #8:
score: 5
Accepted
time: 0ms
memory: 15440kb
input:
16 439163150 802894105 828281100 29854078 492638605 752259707 917086603 810075381 743328523 497018778 360212988 603293784 85540195 33829826 50134176 30721768 1 1 2 3 1 3 7 1 3 4 10 2 9 3 3
output:
2994606234
result:
ok single line: '2994606234'
Test #9:
score: 5
Accepted
time: 0ms
memory: 14788kb
input:
16 95 84 71 72 11 77 100 97 72 93 90 77 1000 33 19 31 1 1 3 3 1 2 5 2 3 8 9 12 5 7 3
output:
1334
result:
ok single line: '1334'
Test #10:
score: 5
Accepted
time: 46ms
memory: 32648kb
input:
100000 51 23 6 31 25 88 47 2 84 90 10 56 97 84 51 74 85 64 21 29 20 21 62 62 36 30 81 82 91 62 53 94 36 10 76 60 49 22 14 32 64 23 39 60 58 90 34 43 53 6 71 24 78 84 86 13 65 18 46 56 79 50 1 66 59 76 26 60 49 91 91 12 13 30 72 70 71 5 64 75 62 86 98 39 69 35 3 34 53 48 41 31 49 93 49 7 20 26 66 68 ...
output:
2529557
result:
ok single line: '2529557'
Test #11:
score: 5
Accepted
time: 61ms
memory: 41512kb
input:
150000 1780 14021 14043 16222 20687 24893 42032 47007 49300 52496 55196 60042 61228 69764 76485 77097 79859 80602 89003 92297 99254 101745 110985 117001 123788 128038 128171 136063 138089 141214 144843 157181 163051 165982 169166 170552 175768 180315 184163 188339 190724 191813 192841 199155 204364 ...
output:
35463479060852
result:
ok single line: '35463479060852'
Test #12:
score: 5
Accepted
time: 64ms
memory: 41680kb
input:
150000 797908089 784987073 46944837 930191726 921098399 310954288 142542503 183158851 498350060 133840827 989090507 980304605 709717903 683657094 583791273 318822313 942189883 219717636 361991649 141603401 9012971 822131679 188198712 434976006 71544379 947141339 106477492 141627901 988298100 4059125...
output:
35453836287189
result:
ok single line: '35453836287189'
Test #13:
score: 5
Accepted
time: 4ms
memory: 14092kb
input:
2000 100 71 65 47 56 12 42 30 54 22 36 97 92 38 84 99 64 57 85 98 39 25 11 17 20 26 66 81 92 64 37 43 35 1 41 42 65 35 71 18 56 6 14 47 95 49 97 10 57 81 59 47 5 69 63 77 95 29 57 38 44 46 81 30 98 21 71 62 55 93 31 10 50 44 8 45 44 57 54 100 37 13 47 94 33 61 70 27 89 78 17 85 23 97 14 21 17 37 82 ...
output:
19842
result:
ok single line: '19842'
Test #14:
score: 5
Accepted
time: 0ms
memory: 15384kb
input:
2000 1 3 5 5 7 8 9 10 11 11 12 12 12 12 12 13 13 13 14 14 15 16 16 16 17 17 18 21 22 22 23 23 23 25 25 25 26 26 27 28 28 28 28 28 28 29 29 29 30 31 31 32 32 33 33 35 36 36 37 37 37 38 39 39 39 40 41 41 41 41 42 42 42 42 43 43 44 45 45 46 46 47 48 48 49 49 50 50 51 51 52 52 52 52 53 53 53 53 54 54 55...
output:
198663
result:
ok single line: '198663'
Test #15:
score: 5
Accepted
time: 0ms
memory: 14808kb
input:
2000 1 1 3 3 4 4 4 5 5 7 7 7 7 7 8 8 9 9 9 10 10 11 11 12 12 12 13 13 14 14 14 14 14 15 15 16 16 16 17 17 17 17 18 18 19 19 19 20 20 21 21 23 24 24 25 25 27 27 27 27 28 28 29 29 29 30 30 31 31 32 32 32 32 33 34 34 34 34 35 35 35 37 38 39 39 40 40 41 42 42 44 44 45 46 46 46 46 48 49 50 51 51 51 51 52...
output:
175767
result:
ok single line: '175767'
Test #16:
score: 5
Accepted
time: 60ms
memory: 30576kb
input:
200000 753 856 722 833 51 114 999 177 365 374 755 761 420 327 354 357 834 691 665 533 926 768 823 753 332 726 832 11 103 774 30 855 982 751 39 32 216 389 561 580 114 315 693 533 993 46 242 178 88 906 710 13 673 884 118 357 610 949 367 712 723 397 918 704 499 308 87 715 696 647 294 161 313 338 693 30...
output:
18276228
result:
ok single line: '18276228'
Test #17:
score: 5
Accepted
time: 50ms
memory: 30620kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
18171535
result:
ok single line: '18171535'
Test #18:
score: 5
Accepted
time: 59ms
memory: 30796kb
input:
199999 823285901 477166963 348450438 320236141 201658155 230106556 298811949 201089971 578905148 921146489 55355606 661735064 864805465 934691341 805255537 654582721 368495076 22691277 28126605 645131210 633602063 438131799 214756248 647514920 480491658 906960147 142206414 397775189 633189604 618961...
output:
17018327325681
result:
ok single line: '17018327325681'
Test #19:
score: 5
Accepted
time: 65ms
memory: 30700kb
input:
199998 787276771 914335740 739025048 444916565 545108873 429907832 521181033 625114241 123679075 635504340 432788154 751979906 270531673 870643710 528513199 630155900 983812400 610529578 918361469 61376025 915950583 491917202 6303438 639611089 695103305 30836351 854978506 863964151 713886031 6278892...
output:
17174054861956
result:
ok single line: '17174054861956'
Test #20:
score: 5
Accepted
time: 61ms
memory: 30908kb
input:
199997 541412948 31954496 577614307 653157996 354253149 377225109 594337307 128057389 106954411 85250057 953326084 107845778 518626668 969193653 882540733 305581838 730205341 84480784 267127777 383392198 8062772 547669300 824385066 911658679 550924598 468293145 447934189 599967513 103929466 18513528...
output:
17135092871559
result:
ok single line: '17135092871559'
Extra Test:
score: 0
Extra Test Passed