QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562733#9265. You Are Given a Treeucup-team1005#AC ✓555ms104268kbC++202.4kb2024-09-13 20:21:052024-09-13 20:21:05

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 22912kb

input:

2
1

output:

4

result:

ok answer is '4'

Test #2:

score: 0
Accepted
time: 2ms
memory: 22376kb

input:

3
1
1

output:

11

result:

ok answer is '11'

Test #3:

score: 0
Accepted
time: 0ms
memory: 22884kb

input:

100
1
2
2
4
5
5
6
8
9
10
6
12
13
14
13
16
16
17
7
20
12
22
23
24
25
19
27
28
29
30
31
32
15
34
35
36
4
38
17
40
41
42
42
44
41
42
47
48
49
42
48
42
42
42
52
56
57
55
59
60
61
62
63
55
65
66
67
68
64
70
71
72
69
74
75
76
77
78
79
78
81
42
83
84
85
86
87
42
89
90
91
92
92
94
95
96
97
98
99

output:

202521

result:

ok answer is '202521'

Test #4:

score: 0
Accepted
time: 5ms
memory: 22420kb

input:

100
1
1
3
4
3
4
6
8
8
10
6
12
7
14
9
9
12
18
18
5
21
22
22
5
25
26
25
21
29
29
7
32
14
10
32
2
37
38
39
38
41
42
41
44
40
42
44
40
13
37
51
52
53
51
55
56
55
58
56
58
39
62
62
2
65
66
67
68
68
67
71
71
66
74
75
75
74
78
13
78
52
82
82
65
85
86
87
87
86
90
90
85
93
94
94
93
97
97
53

output:

214852

result:

ok answer is '214852'

Test #5:

score: 0
Accepted
time: 5ms
memory: 23312kb

input:

100
1
2
1
1
3
6
5
5
4
8
4
4
3
14
10
14
8
13
12
18
8
3
7
1
12
10
9
17
26
30
21
11
29
19
20
25
17
10
9
26
6
40
42
29
2
24
14
25
6
41
47
24
21
46
28
8
30
2
19
41
54
43
23
1
65
21
19
35
58
8
71
59
12
2
13
4
16
7
22
58
26
44
1
12
14
80
19
12
43
77
21
54
41
94
37
61
28
82
30

output:

256559

result:

ok answer is '256559'

Test #6:

score: 0
Accepted
time: 3ms
memory: 22460kb

input:

1000
1
1
1
4
2
3
5
1
7
6
6
12
11
8
6
2
15
18
17
6
21
14
14
3
21
20
1
23
1
3
31
19
26
13
32
24
31
29
23
4
10
16
24
27
28
33
19
39
39
46
40
28
9
7
53
28
13
26
41
52
51
12
60
5
37
7
39
37
21
24
18
67
42
27
42
70
31
8
17
71
58
36
39
38
35
78
34
2
18
67
47
58
11
91
92
36
97
51
44
41
25
21
73
15
45
105
9
...

output:

250730923

result:

ok answer is '250730923'

Test #7:

score: 0
Accepted
time: 3ms
memory: 23312kb

input:

5000
1
2
3
3
5
6
7
6
6
2
7
8
8
7
10
3
15
8
19
4
1
14
8
17
16
24
18
25
28
29
4
15
8
22
30
23
31
15
32
7
8
8
36
15
34
43
16
3
40
49
3
52
38
39
44
42
31
44
59
52
41
40
57
38
41
38
46
43
16
26
61
49
33
57
38
63
28
76
32
18
58
63
43
40
85
39
48
43
88
71
41
68
88
53
43
62
57
77
60
51
24
20
61
58
33
41
23
...

output:

31215816074

result:

ok answer is '31215816074'

Test #8:

score: 0
Accepted
time: 3ms
memory: 22720kb

input:

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

output:

168206066651

result:

ok answer is '168206066651'

Test #9:

score: 0
Accepted
time: 4ms
memory: 23352kb

input:

10001
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
99
100
10...

output:

166766685001

result:

ok answer is '166766685001'

Test #10:

score: 0
Accepted
time: 3ms
memory: 23956kb

input:

30000
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
2
2
2
2
2
2
2
...

output:

4500899935003

result:

ok answer is '4500899935003'

Test #11:

score: 0
Accepted
time: 8ms
memory: 24464kb

input:

40000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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:

10668266620001

result:

ok answer is '10668266620001'

Test #12:

score: 0
Accepted
time: 71ms
memory: 33800kb

input:

50000
1
2
1
2
1
5
1
4
5
3
10
6
6
13
1
1
17
15
2
18
6
3
11
17
21
12
13
7
20
28
10
17
1
7
11
31
30
10
22
14
32
25
21
2
15
20
3
4
13
9
28
41
17
52
15
33
9
46
53
33
2
28
55
17
50
10
24
3
61
26
47
19
8
47
29
29
44
16
11
34
42
56
65
82
34
35
35
83
46
29
9
25
48
71
9
93
79
59
82
99
88
101
19
43
92
53
20
3
...

output:

31258957755757

result:

ok answer is '31258957755757'

Test #13:

score: 0
Accepted
time: 158ms
memory: 47260kb

input:

100000
1
1
3
1
5
5
4
5
7
9
10
4
13
4
14
10
15
7
1
18
13
4
3
10
21
9
12
21
25
4
13
8
33
13
16
34
32
29
8
28
31
1
28
30
29
28
17
16
14
8
1
38
47
9
40
4
1
3
25
6
34
38
6
58
25
25
56
57
39
18
15
58
66
4
18
58
21
24
62
77
71
39
46
24
39
44
19
77
61
76
63
78
93
9
5
50
26
58
56
2
35
3
22
13
104
65
68
57
45...

output:

250198182062171

result:

ok answer is '250198182062171'

Test #14:

score: 0
Accepted
time: 20ms
memory: 25608kb

input:

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
97
98
99
100
1...

output:

166672916675000

result:

ok answer is '166672916675000'

Test #15:

score: 0
Accepted
time: 21ms
memory: 22828kb

input:

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
97
98
99
100
1...

output:

166671666700000

result:

ok answer is '166671666700000'

Test #16:

score: 0
Accepted
time: 19ms
memory: 27432kb

input:

100000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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:

166676666550001

result:

ok answer is '166676666550001'

Test #17:

score: 0
Accepted
time: 252ms
memory: 61568kb

input:

150000
1
1
2
1
1
3
5
5
7
1
3
10
11
3
14
9
17
16
18
14
19
22
5
3
18
16
10
12
28
14
15
18
32
22
4
8
12
12
2
9
25
24
9
4
8
8
33
14
24
5
16
47
5
15
14
29
26
10
11
32
51
43
35
20
22
10
36
55
12
24
38
8
54
55
45
69
51
32
51
78
74
50
57
15
72
35
16
2
17
77
9
31
41
3
42
2
24
63
88
65
40
94
78
19
14
78
103
4...

output:

843453053315146

result:

ok answer is '843453053315146'

Test #18:

score: 0
Accepted
time: 349ms
memory: 74964kb

input:

200000
1
1
3
2
2
6
7
4
5
9
3
1
8
5
1
1
6
15
1
2
13
16
21
20
22
24
3
7
7
30
6
1
16
4
13
21
22
14
14
5
1
11
7
37
35
7
39
29
33
4
48
47
18
43
18
55
9
52
19
49
22
19
16
63
59
51
45
48
24
55
49
65
1
49
44
48
15
21
10
29
55
64
7
23
39
32
36
21
88
61
51
82
8
25
93
79
74
2
38
38
79
69
30
33
92
103
65
103
21...

output:

2000150303801184

result:

ok answer is '2000150303801184'

Test #19:

score: 0
Accepted
time: 44ms
memory: 27912kb

input:

200000
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
99
100
1...

output:

1333358333350000

result:

ok answer is '1333358333350000'

Test #20:

score: 0
Accepted
time: 443ms
memory: 90744kb

input:

250000
1
1
1
2
2
6
3
3
5
6
7
3
2
9
15
16
9
6
17
19
3
12
8
5
24
17
7
3
14
4
8
11
15
4
10
24
2
29
25
1
29
34
5
11
35
45
8
43
4
47
11
5
11
11
20
24
34
1
56
59
44
16
41
25
64
28
58
46
43
36
14
48
21
56
25
71
38
29
57
62
8
75
13
15
30
23
34
34
44
62
88
15
57
35
35
64
72
7
59
100
51
84
86
47
53
32
100
87
...

output:

3907813801646460

result:

ok answer is '3907813801646460'

Test #21:

score: 0
Accepted
time: 535ms
memory: 103340kb

input:

300000
1
2
2
3
5
6
2
2
3
3
3
2
12
7
3
9
14
15
13
2
18
16
12
22
20
22
1
26
6
18
26
26
33
10
8
5
6
7
37
38
41
29
29
40
3
31
9
26
2
39
18
49
23
40
16
49
17
28
56
8
11
54
23
3
33
7
66
55
66
5
25
1
41
13
17
50
14
18
65
12
38
6
39
27
82
64
38
61
15
52
23
54
23
57
87
13
42
54
8
61
22
9
78
13
26
57
63
37
73...

output:

6752565008596418

result:

ok answer is '6752565008596418'

Test #22:

score: 0
Accepted
time: 72ms
memory: 23796kb

input:

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

output:

5414614135404697

result:

ok answer is '5414614135404697'

Test #23:

score: 0
Accepted
time: 55ms
memory: 27852kb

input:

200000
1
1
3
3
5
5
7
7
9
9
11
11
13
13
15
15
17
18
19
18
19
20
23
23
20
25
17
25
29
30
29
30
31
31
35
35
37
37
39
39
41
42
41
42
45
45
47
47
49
49
51
52
52
53
53
56
57
58
58
60
60
62
63
62
57
51
63
68
68
70
71
70
71
74
74
76
76
77
56
77
81
81
83
83
85
85
87
88
88
89
91
89
91
94
94
87
96
98
98
100
10...

output:

1395409937675262

result:

ok answer is '1395409937675262'

Test #24:

score: 0
Accepted
time: 125ms
memory: 40280kb

input:

300000
1
2
3
4
5
6
5
7
9
6
11
12
13
14
15
15
17
18
19
20
21
21
20
22
23
24
23
27
16
30
31
32
33
30
35
12
37
38
39
40
38
42
43
44
45
46
39
48
49
47
51
49
53
54
41
56
57
57
59
60
46
62
63
47
34
17
67
68
68
70
71
72
72
71
75
32
77
78
78
22
53
69
43
84
55
85
87
88
88
90
89
8
93
94
93
96
97
98
99
100
99
...

output:

4981602760265801

result:

ok answer is '4981602760265801'

Test #25:

score: 0
Accepted
time: 133ms
memory: 40336kb

input:

300000
1
2
2
4
5
6
7
6
8
10
7
12
13
14
15
13
17
17
19
18
19
9
23
24
24
11
27
28
28
27
29
30
33
34
31
36
37
33
30
32
39
41
38
36
45
46
45
48
46
29
51
52
15
51
55
55
11
58
59
60
61
62
60
64
64
66
61
68
68
52
5
72
73
14
75
41
38
48
65
40
81
81
9
84
85
85
10
88
89
90
91
92
93
93
95
96
96
94
99
99
94
102...

output:

5072351695734752

result:

ok answer is '5072351695734752'

Test #26:

score: 0
Accepted
time: 169ms
memory: 50424kb

input:

300000
1
2
3
2
5
6
7
8
8
9
9
6
13
14
6
13
17
18
18
8
21
9
7
24
25
25
4
28
3
17
31
3
33
34
35
36
36
35
1
30
41
42
43
41
45
46
16
48
48
49
50
49
49
48
29
56
56
35
59
16
61
45
63
63
41
66
67
66
69
69
61
72
9
48
75
75
29
78
78
78
16
82
83
82
82
82
87
86
83
87
86
61
93
93
21
67
78
35
99
16
83
13
103
104
...

output:

4843222691894230

result:

ok answer is '4843222691894230'

Test #27:

score: 0
Accepted
time: 208ms
memory: 49736kb

input:

300000
1
2
3
3
1
6
7
7
1
10
11
11
11
11
2
16
7
3
16
6
21
21
11
7
7
7
21
11
10
30
30
30
30
21
21
10
37
37
37
37
37
37
37
16
11
21
2
48
48
48
48
48
21
16
6
56
56
56
56
56
56
56
56
6
65
65
65
65
21
16
7
37
21
48
2
76
76
76
76
76
37
3
10
84
84
84
84
84
84
84
84
84
84
84
7
3
48
21
1
100
101
101
101
101
1...

output:

4604563575358215

result:

ok answer is '4604563575358215'

Test #28:

score: 0
Accepted
time: 205ms
memory: 47484kb

input:

300000
1
2
2
2
1
6
6
2
1
10
10
10
2
2
1
16
16
16
16
16
16
10
16
6
1
26
26
26
26
10
26
10
6
10
16
1
37
37
37
37
37
37
26
16
10
37
16
16
2
16
1
52
52
52
52
52
52
52
52
52
6
37
26
2
26
26
1
68
68
68
68
68
68
68
68
68
68
68
37
37
26
68
10
2
16
10
10
6
6
16
10
1
93
93
93
93
93
93
93
93
93
93
93
93
93
93
...

output:

4527686958943404

result:

ok answer is '4527686958943404'

Test #29:

score: 0
Accepted
time: 63ms
memory: 23544kb

input:

300000
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
99
100
1...

output:

4500045000100000

result:

ok answer is '4500045000100000'

Test #30:

score: 0
Accepted
time: 39ms
memory: 37612kb

input:

300000
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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:

4500089999650001

result:

ok answer is '4500089999650001'

Test #31:

score: 0
Accepted
time: 81ms
memory: 30640kb

input:

300000
1
1
3
4
3
4
7
7
9
9
11
11
13
13
15
15
17
18
19
18
17
19
23
23
25
26
27
27
29
26
25
29
33
33
35
35
37
37
39
40
40
39
41
44
44
46
47
48
49
48
41
47
46
49
55
55
57
58
58
60
61
62
62
64
64
66
66
68
68
70
70
72
72
74
74
76
60
61
57
76
81
82
83
82
83
86
81
86
89
89
91
92
91
92
95
95
97
97
99
99
101...

output:

5100011844171302

result:

ok answer is '5100011844171302'

Test #32:

score: 0
Accepted
time: 73ms
memory: 30652kb

input:

300000
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
99
100
1...

output:

4500056250025000

result:

ok answer is '4500056250025000'

Test #33:

score: 0
Accepted
time: 523ms
memory: 99592kb

input:

280000
1
2
3
4
3
2
5
6
5
3
10
11
11
6
12
3
11
1
16
20
6
2
7
6
25
2
4
2
23
13
29
4
2
25
30
24
24
13
4
9
40
25
22
2
26
15
28
3
40
49
5
42
41
40
50
31
51
6
31
50
8
50
54
41
50
27
41
8
30
43
61
71
55
69
19
56
5
41
2
62
69
32
63
83
9
78
53
75
17
89
46
6
68
79
73
10
51
66
14
15
20
11
75
97
12
11
59
37
56
...

output:

5487197856289765

result:

ok answer is '5487197856289765'

Test #34:

score: 0
Accepted
time: 520ms
memory: 100640kb

input:

285000
1
1
2
4
3
6
1
5
5
6
2
2
4
12
6
16
3
18
12
2
20
5
17
3
25
3
7
22
5
23
22
15
28
7
34
35
33
21
37
35
39
20
37
1
28
34
36
34
23
20
11
6
10
35
31
36
17
35
25
12
11
52
47
34
26
19
44
5
61
47
6
62
4
2
67
21
68
69
54
56
68
80
36
79
70
83
58
41
1
67
17
13
44
26
59
74
41
42
17
96
67
43
54
29
41
46
33
6...

output:

5790403762058659

result:

ok answer is '5790403762058659'

Test #35:

score: 0
Accepted
time: 514ms
memory: 100428kb

input:

290000
1
2
3
1
4
6
2
4
6
6
1
8
1
3
2
9
10
7
16
6
18
5
3
14
21
9
15
24
20
22
24
12
24
33
31
15
6
4
31
3
26
19
31
17
12
43
26
38
41
5
2
46
37
1
33
44
42
44
30
23
35
33
62
46
17
52
52
38
33
20
63
71
28
29
4
47
75
34
78
62
68
22
76
51
57
41
50
85
19
76
40
27
38
82
34
77
3
40
3
89
66
4
101
47
59
62
4
16
...

output:

6098833174830677

result:

ok answer is '6098833174830677'

Test #36:

score: 0
Accepted
time: 544ms
memory: 102916kb

input:

295000
1
1
2
1
2
2
5
3
9
5
4
11
2
3
11
7
3
11
17
8
11
9
1
20
21
17
2
16
6
23
13
23
14
31
13
22
9
12
25
30
25
10
19
9
45
28
23
21
45
10
33
15
29
23
43
49
1
57
23
45
38
36
44
40
5
41
55
43
64
23
61
54
19
36
52
56
57
63
14
72
34
70
67
47
77
29
54
52
37
53
11
34
14
86
20
46
46
54
6
70
45
10
80
35
50
21
...

output:

6420399953576328

result:

ok answer is '6420399953576328'

Test #37:

score: 0
Accepted
time: 555ms
memory: 104268kb

input:

299990
1
1
1
2
3
2
7
2
3
8
5
10
2
9
8
12
6
15
5
8
21
15
17
24
7
18
10
14
1
12
17
1
21
11
26
16
26
1
3
30
30
15
8
20
24
35
42
2
14
17
22
35
26
48
6
52
13
19
21
8
34
36
47
23
40
44
64
18
15
25
28
25
12
51
42
14
42
26
77
71
54
53
41
12
28
29
33
63
36
74
64
78
10
54
46
28
90
16
61
48
50
77
98
4
76
68
51...

output:

6749062949204018

result:

ok answer is '6749062949204018'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 22:43:34 | OpenSource Project