P20469 [HackerEarth] You have a tree T (an undirected connected graph containing no cycles) of N nodes rooted at node number 1. Each node is painted either White or Black . You intend to gift this tree to yo
普及-
题目描述

You have a tree T (an undirected connected graph containing no cycles) of N nodes rooted at node number 1. Each node is painted either White or Black . You intend to gift this tree to your girlfriend . However , your girlfriend is rather stubborn and will accept it only if it matches the color scheme the one that she has chosen .

Being the responsible person that you are, you set on re-coloring your tree T. You can do 2 operations on the tree:
1. Paint the i^th node in the color of your choice,i.e,either black or white.
2. Invert the colors of all the nodes in the subtree rooted at i , i.e, for all the nodes in i’s subtree (including i) , change the nodes colored white to black and change the nodes colored black to white.

You want to please your girlfriend and also want to do the least possible work. Output the minimum number of operations that you have to perform to change the color scheme of your tree to the one that your girlfriend wants.

Constraints
1 ≤ N ≤ 100000

Input
The first line contains a single integer N denoting the number of nodes in the tree.
The next N-1 lines contain 2 integers u , v on each line denoting that there is an edge between u and v.
The next line contains N integers,each integer is either 0 or 1. The i^th integer denotes the color of the i^th node. 0 denotes white and 1 denotes black.
The next line contains N integers , each integer is either 0 or 1. The i^th integer denotes the color your girlfriend wants the i^th node to be painted . As above 0 denotes white and 1 denotes black.

Output
Output a single integer:the minimum number of operations needed to performed by you to change the color scheme of your tree to the one your girlfriend wants.

SAMPLE INPUT
4
3 1
3 4
3 2
0 1 0 1
0 0 0 0

SAMPLE OUTPUT
2

输入格式

见题面

输出格式

见题面

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