| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P152PROC - ROUND 2C - Trò chơi trên cây |
Sau khi tính toán tài nguyên ít nhất để di chuyển dân cư, Cooper nhận ra rằng tập hợp các trạm và các không gian liên kết giữa chúng là một cây, khá hứng thú với điều đó anh đã nghĩ ra một trò chơi để thách đố TARS.
Trò chơi trên cây có n nút, đánh số từ 1 đến n, nút gốc là 1, mỗi nút có một giá trị khởi tạo là 0 hoặc 1 và chỉ có thể chứa một trong hai giá trị trên. Chỉ có một thao tác là khi chọn một nút u nào đấy thì giá trị của nút u đảo ngược (0 thành 1 hoặc 1 thành 0), giá trị của nút con giữ nguyên, giá trị nút cháu (nút con của nút con của u) cũng đảo ngược, giá trị nút con của nút cháu u giữ nguyên, giá trị nút cháu của nút cháu u cũng bị đảo ngược và cứ như thế...
Cooper đố TARS giải được thách thức mỗi nút i cần đưa về giá trị đích (có giá trị 0 hoặc 1) với số thao tác ít nhất. Các bạn hãy giúp anh ấy.
Input
Dòng đầu tiên chứa hai số nguyên n (1 ≤ n ≤ 10^5).
n dòng sau mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u, v ≤ n) chỉ ra nút u và v có cạnh nối.
Dòng tiếp theo chứa n số nguyên, số thứ i là giá trị ban đầu của nút i (0 hoặc 1).
Dòng tiếp theo chứa n số nguyên, số thứ i là giá trị cuối cùng của nút i (0 hoặc 1).
Output
In ra số thao tác ít nhất cần được thực hiện.
Example
Input:10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
Output: 2
| Được gửi lên bởi: | adm |
| Ngày: | 2015-03-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
