QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801888#9840. Tree Partitionrotcar07WA 518ms735376kbC++232.5kb2024-12-07 10:30:512024-12-07 10:30:51

Judging History

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

  • [2024-12-07 10:30:51]
  • 评测
  • 测评结果:WA
  • 用时:518ms
  • 内存:735376kb
  • [2024-12-07 10:30:51]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int mod=998244353,N=2e5+5,M=405;
inline void red(int&x){x>=mod&&(x-=mod);}
int n,k;
vector<int> e[N];int fa[N];
void dfs(int p,int f){fa[p]=f;for(int x:e[p]) if(x!=f) dfs(x,p);}
vector<int> L[N];
int nxt[N],pre[N],cnt[N];
int dp[N][M];
main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1,u,v;i<n;i++) cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
    dfs(1,0);
    for(int i=1;i<=n;i++) if(fa[i]>i) L[fa[i]].push_back(i);
    vector<pair<int,vector<int>>>A,B;
    for(int i=0;i<=n+1;i++) nxt[i]=i+1,pre[i]=i-1;
	A.emplace_back(-1,vector<int>(k+1,0));B.emplace_back(-1,vector<int>(k+1,0));
	A.emplace_back(0,vector<int>(k+1,0));A.back().second[0]=1;dp[0][0]=1;
    auto upd=[&](auto&A,int p){
		A.emplace_back(p,A.back().second);
		for(int i=0;i<=k;i++)red(A.back().second[i]+=dp[p][i]);
    };set<int> s;
    for(int i=1;i<=n;i++){
        if(fa[i]<i){
            vector<int> w;int T=0;
            for(int p=pre[i];p>=fa[i];p=pre[p]){
                cnt[p]++;
                if(cnt[p]==1) w.push_back(p);
                else{
                    T++;
                    nxt[pre[p]]=nxt[p];
                    pre[nxt[p]]=pre[p];
                }
            }
            while(T--) B.pop_back();
			reverse(w.begin(),w.end());
			for(int x:w) A.pop_back(),upd(B,x);
        }else s.insert(i);
		auto cmp=[&](const auto&x,const auto&y){return x.first<y.first;};
		for(int z:L[i]) s.erase(z);
		int fi=0,se=0;
		if(!s.empty()){
			fi=*s.rbegin();
			if(s.size()>1) se=*prev(prev(s.end()));
		}
		// cout<<fi<<" "<<se<<' '<<B.size()<<' '<<A.size()<<'\n';
		// for(auto w:B){
		// 	cout<<w.first<<' ';
		// 	for(int z:w.second) cout<<z<<' ';cout<<'\n';
		// }
		// cout<<"???\n";
		// for(auto w:A){
		// 	cout<<w.first<<' ';
		// 	for(int z:w.second) cout<<z<<' ';cout<<'\n';
		// }
		auto it=prev(lower_bound(B.begin(),B.end(),make_pair(fi,vector<int>()),cmp));
		// cout<<it-B.begin()<<"??!!!?\n";
		for(int j=1;j<=k;j++) red(dp[i][j]=B.back().second[j-1]+mod-it->second[j-1]);
		it=prev(lower_bound(A.begin(),A.end(),make_pair(se,vector<int>()),cmp));
		auto jt=prev(upper_bound(A.begin(),A.end(),make_pair(fi,vector<int>()),cmp));
		for(int j=1;j<=k;j++) red(dp[i][j]+=jt->second[j-1]-it->second[j-1]+mod);
		upd(A,i);
		// for(int j=0;j<=k;j++) cout<<dp[i][j]<<' ';cout<<'\n';
		// cout<<"____________\n";
    }
	for(int i=1;i<=k;i++) cout<<dp[n][i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 3
1 2
2 3
2 4

output:

1
2
2

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5952kb

input:

7 7
2 5
3 6
4 5
5 1
1 6
6 7

output:

1
1
0
0
1
2
1

result:

ok 7 lines

Test #3:

score: 0
Accepted
time: 115ms
memory: 666364kb

input:

200000 20
1 2
1 3
1 4
6 5
6 7
6 8
12 9
12 10
12 11
13 14
13 15
13 16
20 17
20 18
20 19
21 22
21 23
21 24
21 25
1 13
6 13
12 13
20 13
21 13
27 26
27 28
27 29
32 30
32 31
32 33
34 35
34 36
34 37
38 39
38 40
38 41
43 42
43 44
43 45
46 47
46 48
46 49
46 50
27 38
32 38
34 38
43 38
46 38
51 52
51 53
51 54...

output:

1
13
176
2319
30068
384955
4875560
61165940
760811301
405332244
246475419
554163687
400425475
668396606
125703386
89953555
995149440
774574469
541392385
429619985

result:

ok 20 lines

Test #4:

score: 0
Accepted
time: 89ms
memory: 666384kb

input:

200000 20
4 1
4 2
4 3
5 6
5 7
5 8
9 10
9 11
9 12
13 14
13 15
13 16
18 17
18 19
18 20
22 21
22 23
22 24
22 25
4 13
5 13
9 13
18 13
22 13
29 26
29 27
29 28
30 31
30 32
30 33
37 34
37 35
37 36
39 38
39 40
39 41
42 43
42 44
42 45
49 46
49 47
49 48
49 50
29 39
30 39
37 39
42 39
49 39
53 51
53 52
53 54
57...

output:

1
14
185
2404
30814
390564
4902418
61000454
752983100
242139987
472863106
929714703
119782922
593712683
609125416
872539629
83372963
639293742
622266226
792288795

result:

ok 20 lines

Test #5:

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

input:

200000 20
1 2
1 3
1 4
8 5
8 6
8 7
9 10
9 11
9 12
16 13
16 14
16 15
19 17
19 18
19 20
24 21
24 22
24 23
24 25
1 16
8 16
9 16
19 16
24 16
27 26
27 28
27 29
33 30
33 31
33 32
36 34
36 35
36 37
39 38
39 40
39 41
45 42
45 43
45 44
46 47
46 48
46 49
46 50
27 39
33 39
36 39
45 39
46 39
53 51
53 52
53 54
57...

output:

1
12
158
2033
25819
324544
4044421
50013717
614106750
503048605
961357590
169415689
710064641
320301852
756985177
967742311
374036652
941058124
588191422
810964435

result:

ok 20 lines

Test #6:

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

input:

200000 20
4 1
4 2
4 3
8 5
8 6
8 7
9 10
9 11
9 12
15 13
15 14
15 16
17 18
17 19
17 20
22 21
22 23
22 24
22 25
4 15
8 15
9 15
17 15
22 15
28 26
28 27
28 29
33 30
33 31
33 32
36 34
36 35
36 37
39 38
39 40
39 41
44 42
44 43
44 45
47 46
47 48
47 49
47 50
28 39
33 39
36 39
44 39
47 39
51 52
51 53
51 54
58...

output:

1
14
185
2408
30925
392609
4934344
61457495
759192354
323633583
518118990
62869842
461787830
235002280
820524864
245863891
813843155
518367835
237965261
480206392

result:

ok 20 lines

Test #7:

score: 0
Accepted
time: 90ms
memory: 666376kb

input:

200000 20
1 2
1 3
1 4
5 6
5 7
5 8
12 9
12 10
12 11
13 14
13 15
13 16
19 17
19 18
19 20
21 22
21 23
21 24
21 25
1 13
5 13
12 13
19 13
21 13
28 26
28 27
28 29
30 31
30 32
30 33
34 35
34 36
34 37
38 39
38 40
38 41
45 42
45 43
45 44
48 46
48 47
48 49
48 50
28 38
30 38
34 38
45 38
48 38
52 51
52 53
52 54...

output:

1
12
162
2139
27808
356888
4528437
56878811
707911548
751808398
222054974
279791496
166135229
747401538
76231320
784949109
746019826
344226740
417885502
996177574

result:

ok 20 lines

Test #8:

score: 0
Accepted
time: 109ms
memory: 671412kb

input:

200000 20
2 1
2 3
2 4
2 5
10 6
10 7
10 8
10 9
14 11
14 12
14 13
14 15
17 16
17 18
17 19
17 20
24 21
24 22
24 23
24 25
26 27
26 28
26 29
26 30
33 31
33 32
33 34
33 35
36 37
36 38
36 39
36 40
45 41
45 42
45 43
45 44
47 46
47 48
47 49
47 50
55 51
55 52
55 53
55 54
58 56
58 57
58 59
58 60
64 61
64 62
64...

output:

1
6
32
163
801
3828
17892
82166
372001
1665172
7387818
32555111
142719061
623206098
716382056
798032235
111522191
907324205
649183234
711010078

result:

ok 20 lines

Test #9:

score: 0
Accepted
time: 83ms
memory: 674140kb

input:

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

output:

1
6
28
123
525
2208
9163
37593
152795
616275
2469825
9844142
39045545
154178384
606270389
378274962
284370698
119748351
103605835
50887914

result:

ok 20 lines

Test #10:

score: 0
Accepted
time: 79ms
memory: 674384kb

input:

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

output:

1
5
25
115
508
2190
9251
38406
157199
636331
2554240
10189169
40463651
160179875
632664753
498284531
840893370
717575251
148116836
172090581

result:

ok 20 lines

Test #11:

score: 0
Accepted
time: 67ms
memory: 672004kb

input:

200000 20
467 400
467 401
467 402
467 403
467 404
467 405
467 406
467 407
467 408
467 409
467 410
467 411
467 412
467 413
467 414
467 415
467 416
467 417
467 418
467 419
467 420
467 421
467 422
467 423
467 424
467 425
467 426
467 427
467 428
467 429
467 430
467 431
467 432
467 433
467 434
467 435
46...

output:

1
5
22
91
362
1400
5294
19643
71709
258203
919227
3243034
11361294
39589640
137398867
475398158
642761809
662785128
484515930
947390198

result:

ok 20 lines

Test #12:

score: 0
Accepted
time: 84ms
memory: 671552kb

input:

200000 20
455 400
455 401
455 402
455 403
455 404
455 405
455 406
455 407
455 408
455 409
455 410
455 411
455 412
455 413
455 414
455 415
455 416
455 417
455 418
455 419
455 420
455 421
455 422
455 423
455 424
455 425
455 426
455 427
455 428
455 429
455 430
455 431
455 432
455 433
455 434
455 435
45...

output:

1
5
22
90
351
1326
4904
17878
64521
231108
822900
2915704
10287661
36166071
126730974
442804706
544933029
374157333
646357026
568707420

result:

ok 20 lines

Test #13:

score: 0
Accepted
time: 68ms
memory: 681648kb

input:

200000 20
1 2
2 3
3 4
4 5
6 7
7 8
1 8
9 10
10 11
11 12
12 13
6 13
14 15
15 16
9 16
17 18
18 19
19 20
20 21
14 21
22 23
23 24
24 25
17 25
26 27
27 28
28 29
29 30
22 30
31 32
32 33
33 34
34 35
26 35
36 37
37 38
38 39
31 39
40 41
41 42
42 43
43 44
36 44
45 46
46 47
47 48
48 49
40 49
50 51
51 52
45 52
5...

output:

1
75128
825619948
444091206
829062655
278521469
237815773
597313479
230618480
802373716
773304989
712677613
237839372
746087668
488970002
17171562
966595372
573931325
526227355
786896120

result:

ok 20 lines

Test #14:

score: 0
Accepted
time: 75ms
memory: 681228kb

input:

200000 20
1 2
2 3
4 5
5 6
6 7
1 7
8 9
9 10
10 11
4 11
12 13
13 14
14 15
8 15
16 17
17 18
18 19
19 20
12 20
21 22
22 23
23 24
24 25
16 25
26 27
27 28
28 29
21 29
30 31
31 32
32 33
33 34
26 34
35 36
36 37
37 38
38 39
30 39
40 41
41 42
42 43
35 43
44 45
45 46
46 47
47 48
40 48
49 50
50 51
51 52
44 52
5...

output:

1
74924
810314840
300962407
478589319
917569974
956848093
997993685
610439861
464664111
727916732
379581436
628134845
967956923
510293112
232570299
200815218
68195908
282199335
336981800

result:

ok 20 lines

Test #15:

score: 0
Accepted
time: 80ms
memory: 680028kb

input:

200000 20
1 2
2 3
3 4
4 5
6 7
7 8
1 8
9 10
10 11
11 12
12 13
6 13
14 15
15 16
16 17
9 17
18 19
19 20
20 21
14 21
22 23
23 24
24 25
18 25
26 27
27 28
22 28
29 30
30 31
31 32
26 32
33 34
34 35
35 36
36 37
29 37
38 39
39 40
40 41
41 42
33 42
43 44
44 45
38 45
46 47
47 48
48 49
43 49
50 51
51 52
52 53
5...

output:

1
74816
802229102
87574505
650723285
656771309
903210078
759853062
497829574
934167620
19659044
378226331
541156973
747002420
518657516
877052886
534925663
978847677
544335234
759285585

result:

ok 20 lines

Test #16:

score: 0
Accepted
time: 84ms
memory: 680908kb

input:

200000 20
1 2
2 3
3 4
5 6
6 7
7 8
1 8
9 10
10 11
11 12
12 13
5 13
14 15
15 16
16 17
17 18
9 18
19 20
20 21
21 22
22 23
14 23
24 25
25 26
26 27
19 27
28 29
29 30
30 31
31 32
24 32
33 34
34 35
35 36
28 36
37 38
38 39
33 39
40 41
41 42
42 43
37 43
44 45
45 46
46 47
47 48
40 48
49 50
50 51
51 52
44 52
5...

output:

1
75374
844131479
167760448
888082583
609134201
948617932
153572706
178975301
328051520
73388765
85180514
272758077
330693357
607354014
41138540
352388304
181035418
700179830
380818871

result:

ok 20 lines

Test #17:

score: 0
Accepted
time: 75ms
memory: 681348kb

input:

200000 20
1 2
2 3
3 4
4 5
6 7
7 8
1 8
9 10
10 11
6 11
12 13
13 14
14 15
15 16
9 16
17 18
18 19
19 20
20 21
12 21
22 23
23 24
24 25
25 26
17 26
27 28
28 29
29 30
22 30
31 32
32 33
33 34
27 34
35 36
36 37
31 37
38 39
39 40
35 40
41 42
42 43
43 44
38 44
45 46
46 47
47 48
41 48
49 50
50 51
45 51
52 53
5...

output:

1
75199
830956574
357426492
112509948
195018850
421113770
193411448
335077876
377273995
475470289
268270822
77011129
165741977
462738002
565429706
856897182
215648623
387452734
155908406

result:

ok 20 lines

Test #18:

score: 0
Accepted
time: 83ms
memory: 669664kb

input:

200000 20
1 2
3 4
6 5
7 8
10 9
12 11
1 7
3 7
6 7
10 7
12 7
13 14
15 16
17 18
19 20
22 21
24 23
13 19
15 19
17 19
22 19
24 19
26 25
27 28
30 29
31 32
33 34
35 36
26 31
27 31
30 31
33 31
35 31
38 37
40 39
42 41
43 44
46 45
47 48
38 43
40 43
42 43
46 43
47 43
49 50
52 51
54 53
56 55
57 58
59 60
49 56
5...

output:

1
25022
313037746
326143902
549774611
529251151
305780838
871118941
935396901
480994057
69357038
565079041
586295267
211954109
885697920
760727702
378813144
362368839
436168000
934195921

result:

ok 20 lines

Test #19:

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

input:

200000 20
1 2
4 3
5 6
7 8
9 10
11 12
1 7
4 7
5 7
9 7
11 7
13 14
16 15
17 18
19 20
21 22
24 23
13 19
16 19
17 19
21 19
24 19
26 25
27 28
30 29
31 32
33 34
36 35
26 31
27 31
30 31
33 31
36 31
38 37
39 40
41 42
43 44
45 46
48 47
38 43
39 43
41 43
45 43
48 43
50 49
51 52
54 53
55 56
58 57
60 59
50 55
51...

output:

1
24979
311962749
864673370
738256178
859803066
635402830
556545282
855791149
536184113
221223658
204825894
469874837
321756201
125751585
559254761
403551309
409720573
327717032
474698395

result:

ok 20 lines

Test #20:

score: 0
Accepted
time: 84ms
memory: 669908kb

input:

200000 20
1 2
3 4
6 5
8 7
10 9
12 11
1 8
3 8
6 8
10 8
12 8
14 13
15 16
18 17
20 19
22 21
24 23
14 20
15 20
18 20
22 20
24 20
26 25
27 28
29 30
31 32
33 34
35 36
26 31
27 31
29 31
33 31
35 31
38 37
40 39
41 42
43 44
46 45
47 48
38 43
40 43
41 43
46 43
47 43
49 50
51 52
53 54
55 56
57 58
59 60
49 55
5...

output:

1
24966
311638113
804407690
904869492
356159781
168039729
736355042
911503299
220764485
699645233
470237319
608891505
629949150
942729056
635359884
2910092
259962910
472382352
237930444

result:

ok 20 lines

Test #21:

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

input:

200000 20
2 1
4 3
6 5
7 8
9 10
12 11
2 7
4 7
6 7
9 7
12 7
14 13
16 15
18 17
19 20
22 21
23 24
14 19
16 19
18 19
22 19
23 19
26 25
28 27
30 29
31 32
33 34
36 35
26 31
28 31
30 31
33 31
36 31
37 38
40 39
41 42
44 43
45 46
47 48
37 44
40 44
41 44
45 44
47 44
49 50
51 52
54 53
56 55
57 58
59 60
49 56
51...

output:

1
24995
312362533
867853624
113718730
125212677
984396175
115757038
835848249
140165564
289892017
653931404
693769958
908935338
786552055
691399344
607827304
79632108
715392002
843837992

result:

ok 20 lines

Test #22:

score: 0
Accepted
time: 76ms
memory: 669880kb

input:

200000 20
2 1
3 4
6 5
8 7
10 9
12 11
2 8
3 8
6 8
10 8
12 8
13 14
16 15
18 17
20 19
22 21
23 24
13 20
16 20
18 20
22 20
23 20
26 25
27 28
30 29
32 31
34 33
36 35
26 32
27 32
30 32
34 32
36 32
38 37
39 40
42 41
43 44
45 46
47 48
38 43
39 43
42 43
45 43
47 43
50 49
52 51
53 54
55 56
57 58
60 59
50 55
5...

output:

1
24987
312162609
366341775
420189392
785247360
653767722
635540731
467217164
82860127
85151628
795586249
157408413
858298559
578884196
687568581
472309769
355929158
351941926
360039605

result:

ok 20 lines

Test #23:

score: -100
Wrong Answer
time: 518ms
memory: 735376kb

input:

200000 400
1 2
1 3
1 4
6 5
6 7
6 8
12 9
12 10
12 11
13 14
13 15
13 16
20 17
20 18
20 19
21 22
21 23
21 24
21 25
1 13
6 13
12 13
20 13
21 13
27 26
27 28
27 29
32 30
32 31
32 33
34 35
34 36
34 37
38 39
38 40
38 41
43 42
43 44
43 45
46 47
46 48
46 49
46 50
27 38
32 38
34 38
43 38
46 38
51 52
51 53
51 5...

output:

1
13
176
2319
30068
384955
4875560
61165940
760811301
405332244
246475419
554163687
400425475
668396606
125703386
89953555
995149440
774574469
541392385
429619985
153707904
106921164
511299642330
27966986635994
669731266114008
11873651792827855
184118549119840838
2646398560695092254
-680580811789272...

result:

wrong answer 23rd lines differ - expected: '198533594', found: '511299642330'