P14933 [HackerEarth] Borys likes to travel.
提高
题目描述

Borys likes to travel.
Now he has a vacation and wants to visit beautiful city Treebourg.
The city consists of n junctions and n-1 roads between them.
Treebourg is the best city for tourists because every junction contains an interesting sight to see.
As Treebourg was designed especially for tourists, there are no unnecessary roads — there is exactly one simple path between each pair of junctions (there is exactly one way to travel between a pair of junctions).

Borys also likes solving problems. Mayor of Treebourg is concerned about how interesting sightseeing tours in his city are. He asks Borys to help to make the tours more interesting.

Borys explored the sights and assigned each of them one integer, describing its beauty.
The i-th junction has a sight with beauty b_i.

Each tour is a simple path between some two distinct junctions.
So, there are $\frac{n \cdot (n-1)}{2}$ tours in total.
A tour is considered interesting if the median (definition) of beauties of all sights in the tour is at least x.
If the number of sights is even then the median is greater of two middle values (any of them in case of a tie).
So, the median of (10, 20, 30, 40) is 30.
The median of (10,11,11,12) is 11.
The median of (10, 20, 30) is 20.

The city can allocate money on repairing at most one sight — its beauty will then increase to any value Mayor chooses.
Borys wants to solve the problem optimally.
He wants to repair a sight, in order to maximize the number of new interesting tours.
Help him to do that.

Find the maximum number of tours that become interesting.

Input format
The first line of the input contains two integers n and x — the number of junctions and the treshold for the tour to be interesting, respectively.

Next n - 1 lines describe the roads of Treebourg.
Each of them contains two integers — junctions connected by a road.
Junctions are numbered 1 through n.

The last line of the input contains $n integers b_1, b_2, \ldots, b_n$ — beauties of sights.

Output format
Print a single integer — the maximum difference between the number of interesting tours after the repair and the initial number of interesting tours.

Constraints

2 ≤ n ≤ 300\,000
0 ≤ x, b_i ≤ 10^9

SAMPLE INPUT
3 3
1 2
2 3
1 2 3

SAMPLE OUTPUT
2

输入格式

见题面

输出格式

见题面

样例输入
1000 900000 23 999 564 28 559 65 926 928 768 336 636 872 372 488 690 262 301 922 678 26 328 456 824 929 954 888 356 974 88 8 221 15 315 456 556 718 351 818 790 762 330 781 981 878 703 309 212 859 600 170 262 132 432 644 806 863 409 652 593 577 456 438 548 814 941 195 69 889 438 554 828 99 112 444 426 140 108 885 238 412 146 119 997 535 589 1000 280 439 51 536 204 665 370 484 158 996 244 841 773 75 304 5 71 68 873 350 255 443 335 415 609 86 266 708 969 935 813 92 39 106 281 556 851 508 289 233 415 941 493 623 568 15 810 432 763 804 803 481 125 331 446 849 576 792 140 763 694 719 451 966 12 966 299 423 501 816 919 62 641 115 422 110 497 902 592 181 453 823 924 308 521 905 157 867 809 804 141 179 672 355 66 148 662 86 338 44 943 132 452 88 267 389 630 289 326 953 638 780 840 893 848 22 309 543 819 262 574 530 634 391 168 237 622 9 623 976 709 683 333 13 517 644 120 176 951 47 775 838 488 241 425 366 685 308 437 481 133 96 756 441 189 302 906 529 405 217 366 856 279 17 329 157 745 463 312 803 353 496 502 952 270 428 80 256 154 602 579 21 528 587 20 309 86 778 4 237 40 742 305 625 749 733 313 125 421 816 665 784 858 964 597 335 611 818 395 367 121 46 471 994 111 948 381 478 887 70 743 88 998 888 424 558 891 60 946 289 130 637 474 655 404 195 671 575 16 460 728 796 646 745 526 862 719 879 649 799 341 330 885 840 413 351 292 658 642 433 988 283 778 438 469 335 530 833 472 607 412 867 717 88 573 843 197 1000 953 62 603 566 162 910 552 543 360 932 399 233 467 625 518 553 627 346 317 984 181 885 336 652 738 205 486 883 393 389 138 434 963 262 87 39 36 434 912 427 320 167 872 19 343 608 714 816 160 992 430 158 554 766 753 151 599 415 993 49 514 190 816 537 740 907 46 737 427 404 463 451 278 383 877 47 774 7 288 929 441 960 464 552 283 907 243 362 980 127 435 8 365 941 352 632 159 555 884 384 368 242 258 206 563 930 151 343 172 36 726 401 723 287 797 744 364 69 974 682 448 441 911 948 683 269 90 167 123 546 132 213 293 831 510 365 371 331 796 599 229 628 899 874 657 901 661 856 588 689 272 569 619 692 54 732 307 91 60 994 843 879 829 325 102 16 820 74 798 103 994 349 67 357 147 231 565 984 179 634 621 40 613 979 729 118 536 924 767 226 808 549 222 212 231 248 669 409 571 914 383 57 949 516 75 28 98 82 252 232 874 494 944 513 837 395 794 781 259 105 637 532 38 528 677 932 392 657 545 116 527 529 914 441 56 25 786 822 470 528 721 725 475 432 263 877 702 908 219 722 650 855 679 423 331 832 509 179 704 391 105 451 811 695 459 404 32 631 570 349 936 977 754 411 177 444 101 279 984 98 358 614 217 495 930 554 43 743 595 362 417 316 687 793 821 804 513 784 418 195 881 861 667 711 710 400 765 61 771 287 442 247 601 251 275 841 460 891 13 884 174 948 127 451 155 139 841 932 965 714 161 51 707 199 584 518 761 154 318 866 290 308 114 509 339 893 598 220 905 325 82 559 990 450 830 437 273 11 624 444 784 594 533 274 228 601 490 27 896 453 586 587 655 828 220 576 251 714 223 224 615 195 658 54 691 477 59 796 213 83 544 587 815 551 264 79 89 567 866 516 208 895 349 810 675 877 747 201 736 520 582 780 934 490 541 611 314 862 297 496 302 196 443 438 306 713 625 504 782 721 47 583 834 309 156 810 61 530 344 752 327 168 506 209 668 162 800 347 676 707 960 88 45 974 178 402 531 406 680 430 116 595 10 898 897 886 708 619 759 209 529 744 741 695 346 498 876 971 136 61 163 865 431 462 14 29 150 890 561 247 193 479 546 841 865 835 248 625 967 214 436 894 240 902 6 376 492 461 325 713 416 231 84 329 735 665 804 487 408 798 605 532 294 240 215 923 628 279 746 475 748 986 540 284 711 895 635 29 131 778 226 297 55 816 214 297 129 798 260 396 291 298 921 340 902 191 25 83 28 855 1000 919 117 966 308 293 489 706 345 412 185 105 555 2 42 132 496 108 400 751 468 683 457 134 996 45 793 429 895 291 24 811 209 703 242 24 347 235 617 859 186 989 34 741 176 240 836 221 396 529 920 896 732 741 780 852 910 395 883 217 722 933 861 573 894 591 462 578 929 802 569 619 64 303 757 556 250 647 838 744 868 193 791 324 73 724 357 517 3 972 673 485 188 687 695 475 633 741 955 31 134 330 440 662 230 156 594 219 760 767 253 522 207 513 940 991 779 767 5 477 1 689 947 251 444 266 853 601 199 339 201 475 606 329 194 123 322 980 137 322 833 974 334 216 608 857 727 495 742 438 511 812 553 966 875 605 971 846 700 650 698 226 962 123 27 327 246 170 720 141 739 238 712 467 989 964 903 211 91 376 77 120 31 45 403 10 764 838 196 776 532 469 239 535 92 401 478 546 17 105 340 168 859 368 473 747 507 295 827 411 762 214 407 185 855 427 626 449 612 152 50 716 481 946 916 990 844 310 224 94 755 67 681 188 447 942 587 706 580 920 842 676 113 860 864 886 406 314 48 62 303 399 394 788 65 81 286 553 187 435 183 582 814 570 107 590 699 960 44 553 659 715 583 174 414 338 76 1000 225 684 900 743 95 681 355 202 386 106 245 567 494 771 769 787 483 884 822 671 235 338 715 682 164 950 103 954 799 196 706 602 257 875 268 596 241 993 956 533 143 785 389 4 933 674 21 587 97 393 543 259 439 658 979 763 96 636 932 412 167 634 913 363 411 927 11 623 857 89 122 723 693 221 801 351 854 939 378 286 939 338 476 640 361 860 744 174 68 939 227 93 817 367 752 329 716 63 825 949 688 212 923 964 428 591 937 318 94 435 62 698 985 156 369 760 211 787 640 651 535 630 57 742 284 867 751 839 549 444 449 501 388 215 377 448 651 451 674 315 410 847 590 501 846 659 845 370 805 898 839 244 976 520 766 19 567 168 254 720 419 751 607 735 701 570 880 352 847 654 660 339 850 144 115 744 119 284 863 651 337 547 376 359 713 904 203 215 734 115 144 494 849 835 645 782 737 680 758 808 692 139 575 646 656 379 862 188 30 701 689 522 7 966 972 837 908 895 504 30 205 526 423 583 484 333 733 808 777 566 450 156 705 541 572 914 149 486 964 164 557 464 285 225 29 384 234 188 915 955 99 413 918 82 978 429 682 201 538 285 959 262 261 465 788 231 152 632 271 489 190 845 835 836 792 926 184 966 826 876 100 341 429 932 74 125 904 397 282 297 585 472 871 68 966 233 508 688 856 603 387 368 686 227 999 280 781 443 118 32 614 391 879 118 379 766 909 400 323 408 973 793 135 344 466 823 724 273 491 911 142 485 19 384 522 367 512 235 363 378 63 970 957 840 898 867 581 722 479 205 610 410 961 920 893 111 938 840 170 15 35 990 547 885 519 7 516 352 434 237 537 462 454 1 256 678 499 812 9 526 191 936 632 233 647 902 359 212 402 926 928 677 455 372 354 677 577 598 882 311 942 708 332 953 420 332 878 516 173 212 860 763 616 75 342 799 391 44 380 839 18 205 110 458 591 212 539 443 500 117 311 404 139 92 49 401 750 198 991 929 206 734 562 435 975 903 166 878 81 832 477 46 776 475 169 544 274 247 106 181 560 986 505 892 72 487 982 724 300 635 578 221 892 639 321 274 458 372 148 667 795 212 362 229 869 609 983 871 952 939 852 87 731 25 93 424 249 872 968 765 200 242 948 644 888 32 663 730 867 948 907 368 995 939 498 553 551 912 503 7 390 513 348 354 192 84 232 384 524 358 922 877 350 138 237 192 977 338 520 361 802 564 550 658 604 285 367 473 210 118 889 799 124 990 772 413 730 414 639 24 958 907 180 572 558 254 233 948 653 994 697 582 41 100 461 849 807 99 684 494 269 237 202 471 832 252 58 742 831 152 664 850 901 897 236 230 542 286 401 44 324 939 26 689 870 954 296 518 171 361 935 701 696 795 70 166 566 329 52 615 480 49 485 554 618 887 15 539 382 276 85 479 433 300 374 51 812 311 22 573 398 647 927 908 373 573 523 5 126 901 78 943 718 933 53 572 465 39 917 916 384 463 83 717 652 257 375 405 445 578 165 167 596 952 316 259 37 237 128 204 670 942 970 344 515 707 33 802 495 882 987 605 153 284 620 980 385 720 770 560 945 240 602 949 666 281 265 229 277 674 182 699 487 339 298 175 287 548 992 167 198 466 145 911 175 301 789 492 482 638 654 717 247 866 823 113 818 938 631 930 629 816 783 373 725 576 195 384 79 36 295 950 218 13 109 617 8 327 310 997 931 121 2 918 397 898 534 620 890 904 785 12 925 267 216 898 643 295 986 821 886 60 319 865 104 424 950 58 276 515 787 904 648 594 525 718 154516 55979 786671 336721 766816 17934 370428 56105 34106 848562 533077 503435 643703 381034 950803 345948 779730 603148 127345 687941 238121 447796 21007 405874 787901 836674 251762 777174 890358 984472 349185 685990 341341 441821 14090 935321 376609 413820 612923 39343 83731 821542 391145 684071 64169 149452 142860 712582 762622 363301 658369 619799 801680 763758 759687 358566 660993 498981 469058 225732 775191 896398 356988 116230 892861 611438 21983 726534 387840 626258 443068 494176 819922 853641 376263 872054 670921 135846 296216 955949 721697 950655 624491 287598 510710 327601 514273 515942 272844 184729 168957 319622 831559 476380 442792 208067 434483 52640 897838 257687 588605 382993 465151 631294 408183 81181 330095 978234 894232 709944 608949 531536 589626 162265 77168 544265 905435 750331 889053 810354 864412 765917 647650 348 115781 958786 460167 845468 465599 562034 101816 987660 429720 255863 788932 804361 461955 727201 715361 612723 207445 439107 655205 277616 696969 924147 159246 752872 294781 965134 305212 555530 255923 890865 705650 991366 594321 455681 124952 541714 266849 778661 963772 769830 638290 945286 782220 708351 817973 159638 58973 798431 464448 603014 996008 363467 429839 668302 972935 622412 659358 977385 317437 532015 362768 176150 846827 612677 55915 239640 320540 554468 354650 910327 455290 93475 647274 491453 105174 430498 555917 942010 327396 672000 902618 564929 325180 84323 828042 165609 341403 443508 713597 330572 930528 400416 69171 526603 459727 143896 111572 913480 279441 982354 698537 466218 576370 322053 337504 546205 792674 44209 280075 403023 54581 718613 608737 475508 419811 685879 197820 877251 207880 894240 604634 853944 764709 321117 288221 334736 734109 248383 509771 308111 601721 330780 585870 653821 308325 572108 399476 886436 692080 909420 786352 690004 551440 470558 360791 908448 7196 20935 618981 939295 128144 815248 697462 261995 211468 609062 898189 559205 522325 562875 602576 961967 401491 699522 149257 566640 894866 173366 727463 879828 38913 553748 187899 864522 68853 416988 615164 52868 951719 759636 593091 657146 928882 733061 523215 226791 759638 827068 450307 772939 636472 53834 401187 746599 972319 809157 387291 98052 497913 942853 390840 761836 28180 373159 378028 779695 649381 606734 340942 397024 353476 670237 346520 570902 16174 370814 244007 456172 756034 989854 588543 402752 749957 806062 226053 590775 188254 354916 994179 186936 42522 838840 157031 43117 924329 500519 780356 47749 905311 915828 332175 807221 624436 149282 906915 509298 600837 660155 795838 604920 963216 375244 175426 769990 649340 217510 447605 884256 270095 464159 438785 902540 210742 227855 941172 794005 355200 765908 192321 415371 418851 642830 301438 853761 206838 265955 856996 624334 500597 866620 402 333 299649 453574 354442 660317 951901 261875 330227 330337 987442 357174 889621 911936 522956 344395 565856 619302 709210 315756 177573 560258 616306 111261 839451 41158 651722 589345 829084 848682 362688 725250 120933 681834 534164 43661 786201 394307 9961 826835 191039 805498 754759 64298 6656 590101 820316 439338 492906 753247 6134 84209 468591 5864 488202 415839 697766 20611 171057 16091 710025 18183 496358 726732 332150 128911 977673 356064 562671 77306 966111 62152 334873 788779 929167 784506 705537 691466 6438 232558 38994 495297 619348 437858 154976 290303 241645 541846 264544 742201 592938 809233 488365 49892 546597 391706 666181 522556 469984 468991 357450 372929 244223 884178 673666 120949 894281 735718 367064 779551 995563 932502 72344 839370 564661 42303 476918 939015 924698 118466 237704 609447 878261 7811 13256 819905 235647 91180 835155 153266 741722 612714 889260 886488 32969 261295 659065 118678 85365 647343 178629 541140 255274 172643 903293 692924 257623 88841 791283 981566 136658 722145 808734 568460 685842 576434 385752 885919 580851 262531 660959 226608 141493 628514 419732 875456 834749 392993 156351 653649 196883 322963 738889 989354 402019 192212 638208 956950 253500 120831 811094 259238 436116 964853 305123 63531 148353 119836 813471 810685 731905 985630 540073 825206 294899 134502 645186 532024 526044 348327 510226 974755 485028 825940 8738 9119 582678 261225 282017 32281 291811 720993 635040 120701 332960 780093 755157 30529 930755 913859 714652 383003 705258 592061 105009 132741 670932 341942 252343 18624 133285 116545 958132 527565 604519 512946 455379 875446 488132 45218 996384 673027 426381 68655 414480 643718 956086 397689 897590 696464 737495 234663 640975 181113 999532 193184 714359 715484 359190 78035 102066 780824 708825 963055 161764 653200 259036 884651 277529 839084 180844 365183 121086 79574 903992 60073 151653 464382 403158 757866 827206 504727 110909 667078 920632 679831 163657 128200 378620 749051 615803 422971 465523 333056 487414 402418 580195 825835 138499 364737 504182 478531 541454 746305 863610 328849 913830 923600 139746 916071 246785 665679 788163 43094 11702 95778 878232 259958 770049 424052 799487 652578 928258 921840 139770 816185 301566 758025 807535 928415 693213 158067 872296 764409 504554 820135 748436 946037 403094 425891 796548 324416 854326 282344 471279 452813 357696 777210 666990 275221 143890 629220 190080 542033 553451 246897 588168 80706 241200 973940 686410 198186 391081 591937 245490 428816 344129 213361 412236 571648 459209 864546 648653 662409 886581 567285 725001 162365 17629 459215 523706 303220 847742 303576 545536 413641 431607 323583 184411 279003 379084 517363 456883 897614 793575 734315 877073 138440 14930 91040 680803 721972 6462 481166 625724 225986 101054 351415 416529 75109 226573 39647 734525 555156 194116 962897 83006 791049 464677 438808 902197 520645 843795 175111 161898 836746 62743 55026 606918 876127 654621 992563 86872 640144 737460 40678 999761 614188 928658 547116 364231 977989 614414 235244 73910 741427 498404 4877 756922 682193 324661 916222 851222 220351 272900 812655 73584 265950 493050 835541 215506 177047 769122 984425 780779 396629 676590 574570 74572 537926 460976 841302 836652 824926 768226 583029 226277 811155 588703 529935 864884 191010 482599 189040 931772 287177 387103 986603 17924 854155 141710 267924 759092 890863 535778 203845 564828 438081 791145 751002 996590 21968 795288 968437 819455 881134 436488 831802 358154 908403 159987 232148 542829 28667 112252 193199 83497 223075 30500 121787 957094 518544 297494 212144 528173 588904 28508 407108 68332 171286 902695 373750 376566 949322 291339 620295 282752 991159 61120 875388 532709 656212 804834 489182 932771 832924 827506 624185 642908 763214 971284 597728 918934 946925 53135 129127 221883 127360 836560 80168 834778 618003 567719 72255 457764 472053 520775 58638 412976 841784 422986 333626 737783 119925 901868 694507 975064 288901 681419 884176 178837 709768 869102 265369 619477 140194 154746 719483 72352 52089 777854 223408 18534 537913 243113 694580
样例输出
19