QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611358#5454. Subtree ActivationDimash33.333333 54ms29920kbC++231.6kb2024-10-04 20:38:022024-10-04 20:38:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 20:38:03]
  • 评测
  • 测评结果:33.333333
  • 用时:54ms
  • 内存:29920kb
  • [2024-10-04 20:38:02]
  • 提交

answer

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = (int)1e9 + 7;

vector<int> g[N];
int s[N], n, sec[N];
ll ans = 0, dp[N][2];       
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];
        assert(dp[to][0] - dp[to][1] + s[to] * 2 >= sec[to] * 2);
        d.push_back({dp[to][0] - dp[to][1] + s[to] * 2, to});
        d.push_back({sec[to] * 2, to});
        m+=2;
    }
    sort(d.rbegin(), d.rend());
    dp[v][0] = dp[v][1] = sum;
    ans += s[v] * 2;
    if(s[v] == 1) {
        return;
    }
    for(int to:g[v]) {
        if(to != d[0].second) {
            sec[v] = max((ll)sec[v], s[to] - dp[to][1] + dp[to][0]);
        } else {
            sec[v] = max(sec[v], sec[to]);
        }
    }
    if(m >= 1) {
        dp[v][0] += d[0].first;
        dp[v][1] += d[0].first;
    }
    if(m >= 2) {
        dp[v][1] += d[1].first;
    }
    // cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << ' ' << sec[v] << ' ' << sum << ' ' << (dp[v][0] - dp[v][1] + s[v] * 2) << ' ' << (sec[v] * 2) << '\n';
}
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: 3ms
memory: 7920kb

input:

3
1 1

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 4.7619
Accepted
time: 3ms
memory: 7644kb

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: 7628kb

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: 7632kb

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: 0ms
memory: 7624kb

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: 3ms
memory: 7716kb

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: 3ms
memory: 7716kb

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: 0
Wrong Answer
time: 3ms
memory: 7916kb

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:

140

result:

wrong answer 1st numbers differ - expected: '138', found: '140'

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 7588kb

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:

128

result:

wrong answer 1st numbers differ - expected: '126', found: '128'

Test #10:

score: 0
Wrong Answer
time: 4ms
memory: 8144kb

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:

18828

result:

wrong answer 1st numbers differ - expected: '18824', found: '18828'

Test #11:

score: 0
Wrong Answer
time: 4ms
memory: 8180kb

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:

18922

result:

wrong answer 1st numbers differ - expected: '18914', found: '18922'

Test #12:

score: 0
Wrong Answer
time: 2ms
memory: 8188kb

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:

18860

result:

wrong answer 1st numbers differ - expected: '18854', found: '18860'

Test #13:

score: 0
Wrong Answer
time: 4ms
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:

18898

result:

wrong answer 1st numbers differ - expected: '18894', found: '18898'

Test #14:

score: 0
Wrong Answer
time: 0ms
memory: 8068kb

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:

18962

result:

wrong answer 1st numbers differ - expected: '18956', found: '18962'

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 8204kb

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:

18886

result:

wrong answer 1st numbers differ - expected: '18882', found: '18886'

Test #16:

score: 0
Wrong Answer
time: 48ms
memory: 29852kb

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:

756688

result:

wrong answer 1st numbers differ - expected: '756550', found: '756688'

Test #17:

score: 0
Wrong Answer
time: 49ms
memory: 29916kb

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:

755788

result:

wrong answer 1st numbers differ - expected: '755654', found: '755788'

Test #18:

score: 0
Wrong Answer
time: 48ms
memory: 27980kb

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:

755928

result:

wrong answer 1st numbers differ - expected: '755830', found: '755928'

Test #19:

score: 0
Wrong Answer
time: 50ms
memory: 29784kb

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:

756954

result:

wrong answer 1st numbers differ - expected: '756822', found: '756954'

Test #20:

score: 0
Wrong Answer
time: 53ms
memory: 29920kb

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:

756314

result:

wrong answer 1st numbers differ - expected: '756212', found: '756314'

Test #21:

score: 0
Wrong Answer
time: 54ms
memory: 29872kb

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:

756066

result:

wrong answer 1st numbers differ - expected: '755930', found: '756066'