QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71810#946. Magic TreeHe_Ren3 163ms46928kbC++232.2kb2023-01-12 01:20:542023-01-12 01:22:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-12 01:22:54]
  • 评测
  • 测评结果:3
  • 用时:163ms
  • 内存:46928kb
  • [2023-01-12 01:20:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXP = MAXN * 20;

namespace SegT {
int ls[MAXP], rs[MAXP], pcnt = 0;
ll mx[MAXP], tag[MAXP];
#define lson(u) ls[u],l,mid
#define rson(u) rs[u],mid+1,r
inline void push_up(int u) {
    mx[u] = max(mx[ls[u]], mx[rs[u]]);
}
inline void upd(int u, ll k) {
    if (!u)
        return;

    tag[u] += k;
    mx[u] += k;
}
inline void push_down(int u) {
    if (tag[u]) {
        upd(ls[u], tag[u]);
        upd(rs[u], tag[u]);
        tag[u] = 0;
    }
}
void insert(int &u, int l, int r, int q, ll k) {
    if (!u)
        u = ++pcnt;

    if (l == r) {
        mx[u] += k;
        return;
    }

    push_down(u);
    int mid = (l + r) >> 1;

    if (q <= mid)
        insert(lson(u), q, k);
    else
        insert(rson(u), q, k);

    push_up(u);
}
void merge(int &u, int l, int r, int v, ll preu, ll prev) {
    if (!u && !v)
        return;

    if (!u) {
        upd(u = v, preu);
        return;
    }

    if (!v) {
        upd(u, prev);
        return;
    }

    if (l == r) {
        mx[u] = max(mx[u], preu) + max(mx[v], prev);
        return;
    }

    push_down(u);
    push_down(v);
    int mid = (l + r) >> 1;
    merge(rson(u), rs[v], max(preu, mx[ls[u]]), max(prev, mx[ls[v]]));
    merge(lson(u), ls[v], preu, prev);
    push_up(u);
}

int n;
inline void insert(int &u, int q, ll k) {
    insert(u, 1, n, q, k);
}
inline void merge(int &u, int v) {
    merge(u, 1, n, v, 0, 0);
}
}

vector<int> g[MAXN];
int a[MAXN], b[MAXN];

int rt[MAXN];
void dfs_res(int u) {
    for (int v : g[u]) {
        dfs_res(v);
        SegT::merge(rt[u], rt[v]);
    }

    if (b[u])
        SegT::insert(rt[u], a[u], b[u]);
}

int main(void) {
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);

    for (int i = 2; i <= n; ++i) {
        int j;
        scanf("%d", &j);
        g[j].push_back(i);
    }

    for (int i = 1; i <= m; ++i) {
        int u, x, y;
        scanf("%d%d%d", &u, &x, &y);
        a[u] = x;
        b[u] = y;
    }

    SegT::n = d;
    dfs_res(1);

    printf("%lld", SegT::mx[rt[1]]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 6124kb

input:

10 9 10
1
1
2
2
3
1
3
8
3
5 4 1
9 4 1
6 8 1
3 1 1
4 9 1
10 1 1
2 6 1
8 7 1
7 9 1

output:

6

result:

wrong answer expected '7', found '6'

Subtask #2:

score: 3
Accepted

Test #10:

score: 3
Accepted
time: 51ms
memory: 18944kb

input:

100000 25000 100000
1
1
2
1
2
1
5
8
8
2
5
2
2
3
1
2
11
10
18
2
9
9
9
8
1
19
18
22
20
17
20
13
30
5
9
8
13
2
19
26
14
31
23
22
2
21
8
1
22
9
50
19
49
42
47
19
21
57
9
52
41
39
10
14
60
56
34
17
18
22
53
5
34
64
29
72
33
11
9
67
58
10
58
70
57
26
65
10
15
64
67
20
26
13
51
81
11
78
40
53
70
33
34
92
7...

output:

12471468294549

result:

ok answer is '12471468294549'

Test #11:

score: 0
Accepted
time: 46ms
memory: 20768kb

input:

100000 20000 100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
9...

output:

10044081452141

result:

ok answer is '10044081452141'

Test #12:

score: 0
Accepted
time: 114ms
memory: 45128kb

input:

100000 90000 100000
1
1
1
1
1
1
1
1
8
1
1
8
11
11
4
4
8
11
4
4
11
4
8
8
24
4
23
4
4
11
23
11
11
1
24
24
11
23
23
23
4
24
24
11
8
11
24
23
8
24
50
1
24
23
4
24
1
4
1
11
11
50
57
23
23
54
53
55
61
23
69
54
67
11
69
24
75
23
1
53
75
1
75
1
75
50
55
61
57
55
55
23
89
8
55
11
77
89
11
24
61
23
1
75
89
67...

output:

44983082712726

result:

ok answer is '44983082712726'

Test #13:

score: 0
Accepted
time: 139ms
memory: 45380kb

input:

100000 90000 100000
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
...

output:

45049819058025

result:

ok answer is '45049819058025'

Test #14:

score: 0
Accepted
time: 163ms
memory: 46928kb

input:

100000 90000 100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
9...

output:

44931255444152

result:

ok answer is '44931255444152'

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 11
Accepted
time: 1ms
memory: 10040kb

input:

1000 500 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
9...

output:

3

result:

ok answer is '3'

Test #16:

score: -11
Wrong Answer
time: 3ms
memory: 10076kb

input:

1000 500 1000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
9...

output:

4

result:

wrong answer expected '38', found '4'

Subtask #4:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 59ms
memory: 12560kb

input:

100000 90000 2
1
1
3
2
1
2
1
5
1
8
11
9
1
8
12
7
1
2
7
6
12
9
16
18
13
10
23
27
26
17
23
10
24
11
21
13
30
1
11
6
13
8
30
15
17
34
39
41
32
29
27
17
21
12
26
33
10
50
29
17
46
33
21
28
47
26
3
67
38
5
10
45
61
70
59
17
46
40
20
58
67
68
15
62
71
71
57
32
81
18
66
7
14
51
67
92
86
38
88
60
45
54
5
59...

output:

36650979037247

result:

wrong answer expected '38521956905095', found '36650979037247'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 1ms
memory: 6980kb

input:

20000 800 60000
1
1
1
2
3
1
7
8
6
1
7
6
1
7
14
16
11
13
14
3
11
11
4
2
5
24
20
24
16
30
15
3
24
31
12
7
2
29
14
25
39
23
16
33
32
33
34
9
13
37
33
23
15
21
28
39
51
19
6
50
54
55
8
40
3
7
34
19
28
15
61
18
22
28
38
15
47
37
42
73
38
61
10
7
30
58
41
43
69
89
62
84
30
68
92
84
43
59
44
75
8
100
83
18...

output:

375093435838

result:

wrong answer expected '386917987664', found '375093435838'

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

0%