#2346. 线图
线图
线图
题目描述
1 线图 1.1 题目描述 九条可怜是一个热爱出题的女孩子。 今天可怜想要出一道和图论相关的题。在一张无向图G 上,我们可以对它进行一些非常有 趣的变换,比如说对偶,又或者说取补。这样的操作往往可以赋予一些传统的问题新的活力。例 如求补图的连通性、补图的最短路等等,都是非常有趣的问题。 最近可怜知道了一种新的变换:求原图的线图(line graph)。对于无向图G = ⟨V, E⟩,它的 线图L(G) 也是一个无向图: • 它的点集大小为|E|,每个点唯一对应着原图的一条边。 • 两个点之间有边当且仅当这两个点对应的边在原图上有公共点(注意不会有自环)。 下图是一个简单的例子,左图是原图,右图是它对应的线图。其中点1 对应原图的边(1, 2), 点2 对应(1, 4),点3 对应(1, 3),点4 对应(3, 4)。 经过一些初步的摸索,可怜发现线图的性质要比补图复杂很多,其中突出的一点就是补图 的补图会变回原图,而L(L(G)) 在绝大部分情况下不等于G,甚至在大多数情况下它的点数和 边数会以很快的速度增长。 因此,可怜想要从最简单的入手,即计算Lk(G) 的点数(Lk(G) 表示对G 求k 次线图)。 然而遗憾的是,即使是这个问题,对可怜来说还是太困难了,因此她进行了一定的弱化。她 给出了一棵n 个节点的树T,现在她想让你计算一下Lk(T) 的点数。 1.2 输入Ḑᓣ 第一行输入两个整数n, k,表示树的点数以及连续求线图的次数。 接下来n −1 行每行两个整数u, v 表示树上的一条边。 1.3 输出Ḑᓣ 输出一行一个整数,表示答案对998244353 取模后的值。 2
1.4 样例输入 5 3 1 2 2 3 2 5 3 4 1.5 样例输出 5 1.6 样例解䞞 如下图所示,左图为原树,中图为L(G),右图为L2(G)。这儿并未画出L3(G),但是由于 L2(G) 有5 条边,因此L3(G) 中有5 个点。 1.7 数据㣗ೈ与约定 测试点 k 测试点 k 1 = 2 6 = 6 2 = 3 7 = 7 3 = 4 8 = 8 4 = 5 9 = 9 5 10 对于100% 的数据,2 ≤n ≤5000。 3
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 3
1 2
2 3
2 5
3 4
5
样例 2
1000 5
1 2
2 3
3 4
3 5
1 6
3 7
3 8
7 9
9 10
10 11
7 12
6 13
12 14
7 15
13 16
8 17
7 18
8 19
9 20
13 21
19 22
8 23
8 24
6 25
11 26
26 27
7 28
3 29
2 30
26 31
7 32
19 33
12 34
22 35
16 36
10 37
32 38
28 39
28 40
22 41
12 42
15 43
4 44
13 45
21 46
38 47
12 48
44 49
35 50
8 51
6 52
50 53
28 54
29 55
34 56
11 57
13 58
45 59
52 60
44 61
28 62
17 63
55 64
9 65
17 66
8 67
24 68
5 69
49 70
4 71
18 72
62 73
15 74
16 75
16 76
15 77
36 78
25 79
5 80
70 81
25 82
73 83
63 84
50 85
33 86
6 87
73 88
85 89
80 90
79 91
89 92
56 93
3 94
63 95
33 96
15 97
91 98
48 99
3 100
45 101
30 102
58 103
96 104
61 105
63 106
75 107
33 108
46 109
37 110
35 111
63 112
24 113
88 114
100 115
56 116
67 117
89 118
94 119
3 120
93 121
23 122
100 123
85 124
37 125
21 126
19 127
79 128
51 129
20 130
123 131
41 132
62 133
11 134
85 135
128 136
70 137
32 138
35 139
5 140
122 141
93 142
60 143
46 144
34 145
97 146
47 147
12 148
116 149
93 150
107 151
49 152
147 153
52 154
4 155
10 156
60 157
47 158
11 159
11 160
47 161
70 162
39 163
69 164
119 165
79 166
17 167
85 168
141 169
25 170
105 171
162 172
111 173
127 174
145 175
145 176
167 177
177 178
176 179
162 180
88 181
160 182
154 183
63 184
76 185
48 186
22 187
47 188
114 189
167 190
91 191
129 192
129 193
8 194
110 195
151 196
171 197
19 198
24 199
58 200
153 201
175 202
28 203
163 204
153 205
193 206
48 207
17 208
34 209
187 210
188 211
156 212
8 213
48 214
67 215
118 216
148 217
203 218
136 219
65 220
106 221
45 222
177 223
164 224
89 225
193 226
84 227
38 228
4 229
33 230
152 231
185 232
113 233
225 234
131 235
161 236
230 237
125 238
110 239
100 240
210 241
205 242
96 243
148 244
243 245
199 246
161 247
182 248
45 249
103 250
82 251
4 252
159 253
246 254
18 255
127 256
130 257
161 258
36 259
29 260
235 261
168 262
204 263
224 264
13 265
55 266
216 267
50 268
61 269
113 270
76 271
15 272
86 273
15 274
11 275
90 276
46 277
190 278
167 279
135 280
111 281
222 282
63 283
76 284
166 285
45 286
78 287
287 288
154 289
118 290
190 291
157 292
166 293
128 294
8 295
293 296
128 297
75 298
177 299
83 300
277 301
112 302
199 303
242 304
143 305
231 306
229 307
247 308
246 309
26 310
219 311
25 312
214 313
61 314
213 315
129 316
183 317
93 318
56 319
11 320
295 321
169 322
116 323
154 324
324 325
271 326
219 327
23 328
62 329
22 330
99 331
43 332
198 333
55 334
195 335
219 336
193 337
157 338
151 339
302 340
248 341
310 342
149 343
228 344
179 345
128 346
1 347
320 348
287 349
25 350
8 351
273 352
163 353
267 354
51 355
355 356
235 357
127 358
164 359
78 360
176 361
25 362
323 363
140 364
328 365
325 366
346 367
223 368
214 369
178 370
134 371
272 372
124 373
16 374
64 375
159 376
292 377
257 378
327 379
30 380
293 381
178 382
6 383
106 384
17 385
176 386
156 387
89 388
44 389
313 390
11 391
269 392
163 393
36 394
67 395
216 396
239 397
8 398
232 399
231 400
175 401
31 402
359 403
72 404
264 405
46 406
174 407
50 408
179 409
216 410
4 411
411 412
260 413
245 414
123 415
197 416
124 417
145 418
242 419
333 420
325 421
146 422
417 423
229 424
20 425
165 426
285 427
282 428
316 429
135 430
364 431
119 432
274 433
123 434
205 435
59 436
207 437
67 438
388 439
367 440
426 441
375 442
234 443
414 444
6 445
154 446
423 447
349 448
92 449
150 450
62 451
236 452
287 453
147 454
242 455
284 456
366 457
175 458
109 459
204 460
333 461
234 462
274 463
117 464
33 465
360 466
182 467
356 468
448 469
37 470
46 471
168 472
318 473
76 474
129 475
166 476
463 477
273 478
150 479
115 480
392 481
126 482
481 483
260 484
282 485
9 486
360 487
475 488
293 489
431 490
201 491
258 492
281 493
167 494
363 495
251 496
196 497
181 498
194 499
398 500
402 501
277 502
465 503
127 504
248 505
259 506
460 507
216 508
262 509
229 510
341 511
257 512
318 513
195 514
299 515
222 516
168 517
217 518
330 519
491 520
428 521
93 522
90 523
33 524
213 525
282 526
464 527
182 528
138 529
87 530
522 531
278 532
449 533
409 534
197 535
247 536
520 537
110 538
227 539
41 540
94 541
339 542
427 543
91 544
338 545
171 546
178 547
386 548
277 549
312 550
285 551
37 552
310 553
427 554
401 555
67 556
443 557
201 558
525 559
386 560
152 561
283 562
153 563
174 564
213 565
339 566
285 567
467 568
418 569
157 570
100 571
415 572
183 573
157 574
29 575
404 576
486 577
213 578
544 579
169 580
435 581
416 582
435 583
417 584
340 585
159 586
150 587
118 588
577 589
573 590
127 591
389 592
100 593
226 594
289 595
326 596
213 597
429 598
416 599
202 600
500 601
438 602
2 603
76 604
580 605
135 606
29 607
545 608
542 609
75 610
340 611
93 612
306 613
497 614
198 615
246 616
418 617
131 618
291 619
303 620
59 621
120 622
202 623
363 624
593 625
623 626
253 627
350 628
200 629
357 630
556 631
552 632
389 633
88 634
79 635
5 636
328 637
481 638
494 639
495 640
377 641
179 642
68 643
210 644
416 645
304 646
551 647
236 648
72 649
37 650
454 651
159 652
398 653
152 654
486 655
530 656
654 657
618 658
179 659
194 660
591 661
32 662
27 663
76 664
630 665
365 666
6 667
107 668
25 669
111 670
116 671
233 672
487 673
104 674
218 675
367 676
425 677
402 678
534 679
55 680
109 681
384 682
526 683
678 684
369 685
82 686
108 687
209 688
101 689
238 690
611 691
499 692
612 693
278 694
463 695
589 696
228 697
285 698
663 699
326 700
499 701
585 702
521 703
131 704
176 705
555 706
401 707
95 708
95 709
147 710
132 711
433 712
433 713
41 714
562 715
381 716
187 717
265 718
30 719
487 720
184 721
245 722
330 723
191 724
205 725
400 726
32 727
592 728
187 729
248 730
332 731
435 732
706 733
281 734
40 735
166 736
84 737
140 738
132 739
38 740
715 741
102 742
429 743
212 744
380 745
701 746
249 747
557 748
631 749
745 750
64 751
172 752
632 753
340 754
559 755
188 756
599 757
214 758
716 759
444 760
523 761
549 762
511 763
158 764
376 765
523 766
292 767
485 768
195 769
430 770
101 771
127 772
210 773
697 774
487 775
750 776
577 777
20 778
155 779
75 780
773 781
144 782
719 783
749 784
39 785
551 786
492 787
189 788
566 789
649 790
62 791
339 792
354 793
418 794
139 795
754 796
186 797
348 798
590 799
230 800
697 801
541 802
396 803
305 804
135 805
236 806
382 807
572 808
567 809
181 810
644 811
683 812
215 813
141 814
408 815
25 816
687 817
779 818
735 819
645 820
393 821
719 822
149 823
578 824
333 825
451 826
683 827
423 828
316 829
504 830
188 831
355 832
139 833
651 834
754 835
559 836
540 837
206 838
58 839
553 840
214 841
460 842
412 843
828 844
749 845
10 846
429 847
579 848
241 849
383 850
593 851
675 852
59 853
420 854
359 855
89 856
56 857
49 858
645 859
345 860
288 861
130 862
500 863
21 864
190 865
213 866
382 867
112 868
261 869
603 870
589 871
827 872
488 873
269 874
107 875
846 876
531 877
243 878
391 879
731 880
179 881
414 882
184 883
191 884
292 885
711 886
407 887
395 888
842 889
93 890
517 891
597 892
676 893
19 894
489 895
288 896
216 897
695 898
435 899
265 900
86 901
727 902
249 903
739 904
884 905
446 906
510 907
214 908
836 909
888 910
519 911
871 912
476 913
31 914
609 915
89 916
271 917
154 918
718 919
362 920
201 921
192 922
159 923
373 924
724 925
432 926
296 927
690 928
536 929
139 930
400 931
589 932
41 933
130 934
439 935
475 936
143 937
388 938
327 939
939 940
271 941
549 942
288 943
365 944
768 945
495 946
321 947
258 948
93 949
528 950
514 951
118 952
372 953
536 954
897 955
107 956
956 957
330 958
558 959
38 960
5 961
613 962
681 963
668 964
239 965
362 966
242 967
179 968
683 969
714 970
655 971
496 972
666 973
961 974
702 975
911 976
342 977
60 978
224 979
315 980
696 981
692 982
331 983
906 984
848 985
838 986
623 987
491 988
331 989
265 990
388 991
428 992
343 993
291 994
750 995
833 996
780 997
587 998
632 999
928 1000
3895749