#2355. 林克卡特树

林克卡特树

林克卡特树

题目描述

CCF NOI 2018 省队选拔赛 第二试林克卡特树(lct) 林克卡特树(lct) 【题目描述】 小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild) 无法自拔,他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做“LCT” 的挑战,它的规则是这样子的:现在有一个N 个点的 树(Tree),每条边有一个整数边权vi ,若vi ≥0,表示走这条边会获得vi 的收益;若 vi < 0 ,则表示走这条边需要支付−vi 的过路费。小L 需要控制主角Link 切掉(Cut) 树上的.恰.好K 条边,然后再连接K 条边权为0 的边,得到一棵新的树。接着,他会选 择树上的两个点p, q ,并沿着树上连接这两点的简单路径从p 走到q ,并为经过的每 条边支付过路费/ 获取相应收益。 海拉鲁大陆之神TemporaryDO 想考验一下Link。他告诉Link,如果Link 能切掉 合适的边、选择合适的路径从而使.总.收.益- .总.过.路.费最大化的话,就把传说中的大师之 剑送给他。 小L 想得到大师之剑,于是他找到了你来帮忙,请你告诉他,Link 能得到的.总.收 .益- .总.过.路.费最大是多少。 【输入格式】 从文件lct.in 中读入数据。 输入第一行包含两个正整数N, K,保证0 ≤K < N ≤3 × 105。 接下来N −1 行,每行包含三个整数xi, yi, vi,表示第i 条边连接图中的xi, yi 两点, 它的边权为vi。 【输出格式】 输出到文件lct.out 中。 输出一行一个整数,表示答案。 【样例1 输入】 5 1 1 2 3 2 3 5 2 4 -3 4 5 6 第7 页 共10 页

CCF NOI 2018 省队选拔赛 第二试林克卡特树(lct) 【样例1 输出】 14 【样例1 解释】 一种可能的最优方案为:切掉(2, 4, −3) 这条边,连接(3, 4, 0) 这条边,选择 (p, q) = (1, 5)。 【样例2】 见选手目录下的lct/lct2.in 与lct/lct2.ans。 【子任务】 • 对于10% 的数据,k = 0 ; • 对于另外10% 的数据,k = 1 ; • 对于另外15% 的数据,k = 2 ; • 对于另外25% 的数据,k ≤100 ; • 对于其他数据,没有特殊约定。 对于全部的测试数据,保证有1 ≤N ≤3 × 105, 1 ≤xi, yi ≤N, |vi| ≤106 。 【提示】 题目并不难。 第8 页 共10 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 1
1 2 3
2 3 5
2 4 -3
4 5 6
14

样例 2

1000 25
862 821 -993
842 824 -210
400 964 -62
818 839 203
518 727 -192
918 781 247
971 793 702
725 536 28
567 888 -710
687 256 728
924 208 841
715 829 374
311 959 -100
211 903 104
687 158 -120
741 405 139
966 937 -330
7 106 190
403 125 250
318 392 -256
357 543 -745
533 848 219
667 519 -217
714 604 -96
656 523 170
787 144 -995
142 818 -619
460 541 637
342 382 755
386 382 -12
684 777 -550
122 502 -365
853 987 613
954 169 -715
757 933 774
203 880 -966
284 566 693
131 467 542
114 70 -386
612 963 106
511 28 -365
592 961 -650
137 468 604
202 72 412
381 729 400
943 350 550
197 922 641
92 373 -473
527 43 567
296 1000 230
176 139 -43
410 477 369
998 655 633
457 33 -319
886 282 -86
906 177 -970
116 648 570
25 609 679
994 806 39
129 279 -468
41 471 -396
200 730 -712
944 563 -734
329 255 55
641 322 185
494 725 -269
228 879 106
791 181 -653
187 985 -876
213 30 -458
640 473 488
226 411 701
249 338 -934
515 409 -770
621 195 142
155 966 544
289 788 -599
733 496 548
870 37 -796
74 326 615
960 969 -1000
514 254 -355
279 879 560
457 189 402
624 696 135
764 123 837
892 127 630
483 952 237
604 789 588
146 790 917
6 864 787
478 471 -525
961 708 -594
907 178 -589
276 928 739
363 741 113
834 960 929
686 431 -598
20 425 -693
329 714 -714
361 196 -138
203 456 622
882 843 -227
124 160 303
939 724 882
830 547 -353
196 676 793
614 224 412
447 455 -742
706 321 923
391 691 407
498 255 293
733 955 -207
196 102 938
398 221 -387
659 399 -901
428 815 903
618 47 -361
463 543 693
849 795 -407
371 816 -726
96 417 -201
204 899 920
107 29 380
772 777 148
837 628 289
413 588 895
395 776 -439
519 133 -52
470 339 345
700 285 -722
334 410 -850
687 674 -722
786 813 970
778 957 845
590 989 102
336 992 361
593 899 300
252 645 225
164 509 -871
912 189 538
575 511 -516
725 437 114
447 641 678
407 461 100
698 590 -263
469 854 138
776 541 -328
561 686 -209
473 224 -56
465 461 -238
576 307 -689
923 793 503
950 584 -484
552 118 -711
891 496 -343
644 724 622
914 209 -627
856 104 744
166 326 912
590 36 -813
653 481 336
961 586 92
184 526 -703
638 123 -350
670 266 -482
895 710 -157
156 263 91
701 397 997
907 908 -370
588 791 810
734 460 226
950 686 986
577 143 281
385 723 207
714 970 688
944 60 840
661 59 833
68 958 31
837 813 -629
328 50 -72
619 929 -351
453 822 275
537 258 231
80 506 -96
265 312 -330
738 75 -295
378 68 702
435 457 52
555 170 534
681 223 731
502 577 -676
581 448 802
427 760 615
3 8 845
545 380 -930
853 211 -126
937 335 658
514 553 -984
862 107 -467
604 703 -694
413 399 633
117 97 -344
88 19 -184
352 132 430
242 478 81
148 944 -315
906 83 844
985 300 120
770 83 -125
252 807 1
919 734 -150
126 562 222
664 686 138
324 193 -46
92 196 -843
293 832 -569
642 888 386
265 127 -762
871 763 910
301 183 665
167 732 500
740 742 510
198 951 -608
608 140 -642
305 816 150
508 835 -788
757 737 -208
719 290 -935
490 20 -772
683 382 158
731 629 393
947 164 733
605 386 791
191 838 -907
548 567 -691
579 853 805
796 691 665
790 441 -291
580 658 501
325 804 -118
159 415 541
603 285 -350
612 525 -915
990 403 377
130 379 -152
447 206 -744
497 963 238
27 299 -424
157 932 -370
568 904 843
400 33 986
170 337 -695
350 652 -482
761 597 -179
106 755 195
914 634 -775
667 58 -646
428 130 -818
607 332 -295
179 578 867
503 924 208
618 87 795
338 471 225
252 51 -412
191 856 40
310 79 -649
775 181 192
327 75 790
516 222 -216
138 945 285
319 629 428
619 694 386
822 483 944
183 154 335
750 783 -316
141 442 -799
847 746 -119
564 88 895
873 398 924
876 717 518
898 655 -530
976 423 -340
602 8 639
32 943 -71
41 784 -827
512 34 72
448 493 725
565 767 -61
68 698 584
726 735 873
603 627 -411
144 901 717
540 301 184
513 422 -311
714 10 650
182 96 -258
170 518 189
48 826 340
863 303 408
669 366 921
129 418 -961
843 994 -704
542 586 8
749 329 -455
647 142 -377
445 487 -585
726 246 607
572 208 -762
578 254 299
168 697 -431
260 858 -309
233 866 69
690 891 -731
892 630 379
423 649 -767
585 393 -186
245 501 849
649 194 594
471 143 903
352 907 -439
438 980 672
148 899 294
70 823 -335
248 194 182
106 501 -985
140 733 -87
964 665 -382
254 921 701
307 124 504
714 345 -880
341 500 935
208 486 567
802 741 159
811 670 754
151 52 972
450 43 -300
13 851 -151
518 145 -523
227 741 82
214 295 478
695 745 -476
718 299 361
256 235 486
539 621 587
856 152 254
256 564 -717
508 994 -802
155 264 -914
710 744 682
346 884 533
920 410 269
198 347 -148
103 867 -774
6 183 189
833 615 -898
297 360 964
272 569 -829
196 48 -118
575 324 500
251 658 -797
373 722 733
610 644 56
78 298 7
912 406 -155
13 457 654
740 144 899
531 972 -832
46 462 -403
922 483 637
263 73 260
153 484 -992
825 114 922
665 308 662
655 358 -49
854 167 -171
297 489 -415
808 174 -689
430 855 -951
580 247 455
677 948 564
792 490 -614
496 108 588
994 585 771
301 299 -494
302 899 970
782 78 -297
649 77 -897
803 599 -171
369 491 -458
776 966 -961
345 143 -510
542 846 47
997 356 380
712 12 676
545 25 105
420 900 943
663 83 817
384 639 -955
679 133 714
565 698 -450
450 987 431
805 256 -668
437 916 -451
616 30 -145
686 273 -503
720 642 577
164 149 76
723 281 345
668 345 277
704 5 -153
544 671 374
13 574 430
996 888 877
112 552 -667
849 546 140
321 20 -613
246 773 -192
862 642 -896
335 404 -6
798 761 563
526 353 -32
940 52 -966
673 908 -123
123 78 -945
993 946 71
440 804 -908
128 497 250
687 275 192
725 323 -890
825 291 -727
855 1 523
353 315 821
760 62 -949
230 347 245
516 792 998
335 1 -907
163 432 61
609 261 -435
442 496 -379
39 735 649
647 366 -362
451 896 694
401 709 -623
4 81 -430
215 892 967
472 512 738
917 447 -381
251 876 378
749 109 -404
376 735 716
242 136 -13
192 94 116
143 114 495
478 93 542
157 256 -26
618 49 -78
250 758 -511
144 272 56
827 876 57
199 345 -89
250 859 -974
273 934 -931
736 841 764
745 739 -127
946 230 627
433 766 -489
738 743 512
84 595 775
995 697 980
688 362 -764
190 790 -937
760 464 -436
340 220 330
353 119 -24
526 477 -640
529 747 409
309 596 -908
428 694 -411
171 235 -961
773 769 774
678 433 164
715 974 393
892 885 -418
316 196 -204
290 61 -960
62 328 515
261 693 747
534 456 -787
366 812 -187
420 227 19
841 76 -811
731 180 117
387 782 21
482 442 696
274 369 839
546 368 841
318 914 -133
898 533 -208
143 24 958
614 538 125
797 513 -823
174 984 215
305 867 834
794 560 -886
510 954 731
559 860 -66
280 318 119
285 223 -798
506 594 -130
694 987 -687
944 913 -77
642 713 267
330 86 -56
95 495 -648
436 584 648
61 758 -988
398 732 675
271 73 -137
55 448 -788
534 432 268
633 906 -889
528 277 863
695 542 809
512 656 -517
977 365 519
416 410 -57
10 632 -493
420 458 345
382 326 827
408 512 909
658 277 -711
362 450 -588
636 543 147
643 446 -415
928 625 -747
746 659 -141
480 779 612
155 354 -292
260 705 901
832 258 -902
975 863 101
66 682 -25
803 974 -192
591 314 -385
777 454 131
771 170 665
255 496 -557
808 89 -503
925 509 -90
808 60 -937
853 598 -508
12 796 -359
944 934 -242
871 498 523
562 772 654
409 741 634
800 360 777
269 5 920
254 381 -515
913 680 -224
159 18 -385
637 83 -407
905 447 -926
427 617 763
426 324 -828
374 796 704
657 358 863
143 730 -676
256 807 250
84 632 278
774 586 25
478 339 -228
691 756 520
38 178 -58
323 819 -218
716 59 178
893 183 716
817 649 -988
524 977 -583
522 134 889
419 857 -285
229 125 -633
890 665 494
86 691 198
162 396 -905
416 808 -239
489 836 -498
461 956 35
550 131 781
367 685 141
56 83 252
814 492 74
801 679 646
39 833 871
466 978 532
883 254 767
381 91 -535
573 55 -175
908 260 940
922 98 816
486 961 613
289 838 -289
615 753 223
180 682 251
780 689 279
338 897 -763
838 35 -734
276 211 -389
237 584 511
388 156 88
750 837 355
548 879 -154
418 793 660
896 265 -108
814 611 -192
551 550 190
2 376 -602
621 679 650
258 699 -240
442 260 739
276 31 -152
82 818 -874
887 462 -157
387 396 697
868 645 -667
575 170 -490
133 826 -247
796 369 65
675 782 -416
11 344 125
854 850 -778
580 545 -74
21 246 772
313 209 356
105 599 32
486 287 -874
575 157 -816
559 9 665
139 930 -896
313 857 -505
35 929 703
134 973 683
554 650 476
882 549 982
90 485 -295
295 848 8
385 742 420
335 249 -782
535 21 -934
877 818 -164
491 14 784
653 235 -908
886 879 887
340 865 -448
151 68 118
483 323 985
34 539 167
312 180 -611
442 631 973
995 382 -742
332 505 476
969 351 -725
362 54 -686
643 654 -243
638 847 182
986 492 -408
139 957 226
547 285 -953
199 165 999
542 101 -341
942 198 -239
317 918 50
255 804 426
256 217 -873
452 80 809
421 476 -254
556 316 -234
582 517 -150
852 274 71
254 666 -426
258 101 -687
58 121 -225
412 950 408
468 613 -349
355 644 -21
348 72 636
780 70 68
343 966 225
254 565 -877
124 583 5
589 100 296
941 255 -671
853 67 -229
877 639 -744
331 284 900
667 709 653
576 232 554
878 81 752
170 982 -193
692 159 925
467 872 -174
26 719 82
46 213 803
935 777 945
44 652 -226
45 859 -471
629 103 -743
670 726 245
5 125 152
607 150 543
583 240 889
275 395 264
40 87 179
51 424 961
372 360 -469
878 48 -115
996 422 -440
147 381 -191
764 963 389
222 421 403
794 587 -183
981 564 789
16 515 -652
346 747 -225
869 175 -909
275 783 -892
623 67 512
938 922 421
45 87 502
133 370 348
186 969 -176
262 819 -52
159 278 757
903 691 303
230 751 624
899 831 -136
261 383 753
338 495 -370
65 395 243
793 389 -286
268 665 722
811 244 313
635 547 310
459 791 -406
77 488 672
902 972 -599
526 881 732
73 759 436
748 342 -781
283 9 748
934 962 -441
726 235 842
606 926 -179
115 834 526
924 479 433
803 438 -46
506 523 -381
765 528 58
31 844 -887
988 6 -703
604 96 151
381 218 395
421 22 162
270 694 927
449 734 -316
979 556 -219
304 76 843
467 48 -332
474 514 -793
770 909 -274
504 732 990
754 718 908
973 958 503
991 116 -906
750 915 -826
839 340 -42
809 344 -353
587 235 764
773 292 -259
744 233 -254
804 350 -79
931 741 339
397 488 264
242 360 426
732 834 314
59 514 -775
225 256 -55
510 871 469
672 696 -788
933 64 177
320 442 69
443 522 268
34 382 -955
243 498 81
349 571 -279
802 886 -118
767 507 -531
1000 319 962
808 960 784
532 518 -239
113 579 -791
143 520 957
895 824 -766
662 235 -285
422 212 -897
51 69 -610
314 668 141
471 149 -555
971 668 -311
657 529 86
249 253 -533
997 56 723
721 815 745
530 810 -774
957 993 -816
439 135 -819
320 582 88
646 10 -339
936 994 -322
338 234 326
172 355 -176
965 458 510
944 210 -70
294 855 -735
226 146 -405
626 559 700
187 493 -124
175 738 113
622 542 -338
671 713 263
578 475 440
239 820 -647
384 259 -746
689 762 -36
966 183 947
968 60 270
972 96 119
967 312 851
745 874 849
450 153 -661
219 498 24
820 750 -381
289 57 18
241 686 636
810 272 -816
55 663 641
53 525 14
247 499 267
662 148 8
85 111 -801
135 847 635
870 17 -160
841 6 363
327 197 917
867 303 -195
845 75 211
232 671 853
56 850 -156
639 161 -324
949 777 665
733 427 -509
333 247 -959
261 683 -143
310 610 -670
216 259 96
269 78 -624
146 889 113
516 606 40
905 56 463
63 251 243
231 757 -230
494 875 212
880 309 -45
644 735 49
877 696 -909
471 238 -953
386 434 -981
768 995 645
775 461 -489
677 391 -703
607 78 -938
421 306 451
112 138 4
521 149 208
7 911 -438
25 757 850
139 901 -982
558 685 954
408 394 116
773 288 -840
660 376 716
588 448 346
492 422 411
723 358 725
978 851 -920
15 687 86
286 115 811
678 949 -126
953 641 -858
94 275 -605
589 195 647
657 707 -965
208 500 -138
444 59 752
267 348 -453
39 936 -702
262 700 233
574 476 -331
621 26 750
767 602 -877
42 793 974
357 872 529
552 154 -140
744 731 712
610 336 599
896 799 263
562 201 909
607 570 -977
462 755 -600
316 17 -695
8 673 -200
313 120 -675
524 871 806
511 23 -767
488 205 -55
427 375 -59
414 158 -320
311 59 -299
654 30 986
651 717 -901
173 527 -923
284 975 943
159 106 775
210 601 -687
429 366 297
111 248 -764
10 711 -663
702 343 687
268 975 -330
860 10 -189
11 679 391
768 257 -467
242 364 -108
861 884 167
991 620 -239
785 135 -982
790 154 300
313 894 -619
110 154 484
884 349 -638
557 579 985
546 716 -566
487 910 -283
338 438 -980
932 597 -289
43 117 -441
600 262 254
951 47 729
620 397 440
433 346 23
757 447 276
84 188 -404
402 885 -442
185 759 206
71 114 -214
752 35 -621
500 644 -833
650 553 -351
203 377 605
728 788 386
360 725 -385
90 924 975
513 927 -407
99 672 -986
786 359 -845
840 947 791
672 924 192
422 614 564
613 194 -522
914 932 -94
630 935 -662
197 390 149
816 983 212
156 850 -497
134 213 581
534 381 -312
109 236 -53
392 207 622
552 999 923
779 788 -313
442 72 787
861 487 -377
856 406 536
787 367 842
347 918 -43
828 167 -608
77 467 589
665 568 357
96035