QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611396 | #5454. Subtree Activation | Dimash | 100 ✓ | 55ms | 29160kb | C++23 | 1.2kb | 2024-10-04 20:51:18 | 2024-10-04 20:51:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 12, MOD = (int)1e9 + 7;
int n, s[N];
ll dp[N][2], f[N], ans = 0;
vector<int> g[N];
void calc(int v) {
s[v] = 1;
ll sum = 0;
vector<pair<ll, ll>> d;
int m = 0;
for(int to:g[v]) {
calc(to);
s[v] += s[to];
sum += dp[to][1];
d.push_back({dp[to][0] - dp[to][1] + s[to] * 2, to});
d.push_back({f[to], to});
}
ans += s[v] * 2;
if(s[v] == 1) return;
dp[v][0] = dp[v][1] = sum;
sort(d.rbegin(), d.rend());
dp[v][0] += d[0].first;
dp[v][1] += d[0].first + d[1].first;
for(int to:g[v]) {
if(to == d[0].second) {
f[v] = max(f[v], f[to]);
} else {
f[v] = max(f[v], dp[to][0] - dp[to][1] + s[to] * 2);
}
}
}
void test() {
cin >> n;
for(int i = 2; i <= n; i++) {
int p;
cin >> p;
g[p].push_back(i);
}
calc(1);
cout << ans - max(dp[1][0], dp[1][1]) << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 4.7619
Accepted
time: 0ms
memory: 7700kb
input:
3 1 1
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 4.7619
Accepted
time: 3ms
memory: 7584kb
input:
8 1 2 1 1 5 3 4
output:
20
result:
ok 1 number(s): "20"
Test #3:
score: 4.7619
Accepted
time: 3ms
memory: 7720kb
input:
8 1 2 1 4 5 4 4
output:
20
result:
ok 1 number(s): "20"
Test #4:
score: 4.7619
Accepted
time: 3ms
memory: 7920kb
input:
40 1 1 1 1 1 1 1 1 1 7 11 10 12 13 15 16 16 15 18 20 21 21 21 21 21 21 21 21 21 6 18 28 12 34 22 6 15 23 32
output:
130
result:
ok 1 number(s): "130"
Test #5:
score: 4.7619
Accepted
time: 3ms
memory: 7932kb
input:
40 1 1 1 1 1 1 1 1 1 10 9 12 8 14 15 16 17 12 17 19 21 21 21 21 21 21 21 21 21 23 26 15 9 6 27 32 5 11 8
output:
132
result:
ok 1 number(s): "132"
Test #6:
score: 4.7619
Accepted
time: 0ms
memory: 7632kb
input:
40 1 1 1 1 1 1 1 1 1 6 11 12 13 8 15 15 16 18 17 18 21 21 21 21 21 21 21 21 21 23 13 17 8 20 6 24 27 38 36
output:
132
result:
ok 1 number(s): "132"
Test #7:
score: 4.7619
Accepted
time: 0ms
memory: 7628kb
input:
40 1 1 1 1 1 1 1 1 1 10 11 7 13 14 15 16 17 18 18 18 21 21 21 21 21 21 21 21 21 25 11 13 13 3 24 11 25 35 28
output:
132
result:
ok 1 number(s): "132"
Test #8:
score: 4.7619
Accepted
time: 0ms
memory: 7700kb
input:
40 1 1 1 1 1 1 1 1 1 10 11 12 11 14 14 14 17 16 16 20 21 21 21 21 21 21 21 21 21 17 22 25 14 25 29 23 1 17 14
output:
138
result:
ok 1 number(s): "138"
Test #9:
score: 4.7619
Accepted
time: 3ms
memory: 7648kb
input:
40 1 1 1 1 1 1 1 1 1 7 11 12 12 13 14 13 16 18 19 20 21 21 21 21 21 21 21 21 21 17 8 17 33 27 3 34 20 4 10
output:
126
result:
ok 1 number(s): "126"
Test #10:
score: 4.7619
Accepted
time: 0ms
memory: 8184kb
input:
5000 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 1...
output:
18824
result:
ok 1 number(s): "18824"
Test #11:
score: 4.7619
Accepted
time: 4ms
memory: 8176kb
input:
5000 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 1...
output:
18914
result:
ok 1 number(s): "18914"
Test #12:
score: 4.7619
Accepted
time: 4ms
memory: 8400kb
input:
5000 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 1...
output:
18854
result:
ok 1 number(s): "18854"
Test #13:
score: 4.7619
Accepted
time: 4ms
memory: 8196kb
input:
5000 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 1...
output:
18894
result:
ok 1 number(s): "18894"
Test #14:
score: 4.7619
Accepted
time: 0ms
memory: 8096kb
input:
5000 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 1...
output:
18956
result:
ok 1 number(s): "18956"
Test #15:
score: 4.7619
Accepted
time: 0ms
memory: 8368kb
input:
5000 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 1...
output:
18882
result:
ok 1 number(s): "18882"
Test #16:
score: 4.7619
Accepted
time: 55ms
memory: 26252kb
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:
756550
result:
ok 1 number(s): "756550"
Test #17:
score: 4.7619
Accepted
time: 49ms
memory: 28612kb
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:
755654
result:
ok 1 number(s): "755654"
Test #18:
score: 4.7619
Accepted
time: 51ms
memory: 28528kb
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:
755830
result:
ok 1 number(s): "755830"
Test #19:
score: 4.7619
Accepted
time: 48ms
memory: 29160kb
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:
756822
result:
ok 1 number(s): "756822"
Test #20:
score: 4.7619
Accepted
time: 55ms
memory: 28364kb
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:
756212
result:
ok 1 number(s): "756212"
Test #21:
score: 4.7619
Accepted
time: 55ms
memory: 26404kb
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:
755930
result:
ok 1 number(s): "755930"