Nhà máy điện JOI có \(N\) trạm được đánh số từ \(1\) đến \(N\). Các trạm được nối với nhau bằng \(N-1\) dây dẫn. Dây dẫn thứ \(i\) (\(1 \le i \le N-1\)) nối trạm \(A_i\) với trạm \(B_i\) và có thể đi qua theo cả hai chiều. Có thể đi từ một trạm bất kỳ đến bất kỳ trạm nào khác bằng cách đi qua các dây dẫn.

Mỗi trạm có nhiều nhất một máy phát điện. Mỗi máy phát điện có một công tắc; ban đầu, tất cả các công tắc đều ở trạng thái tắt (OFF). Bạn là giám đốc nhà máy và có thể chọn một số máy phát điện để chuyển công tắc của chúng sang trạng thái bật (ON). Bạn cũng được phép không chọn máy nào.

Các máy phát điện có những tính chất sau:

• Giả sử các trạm \(x,y,z\) đều có máy phát điện và có thể đi từ \(x\) đến \(y\), rồi từ \(y\) đến \(z\), theo thứ tự đó mà không đi qua cùng một dây dẫn hai lần. Nếu công tắc của máy phát điện tại \(x\) và \(z\) đều bật thì máy phát điện tại \(y\) bị hỏng.
• Một máy phát điện hoạt động nếu công tắc của nó bật và nó không bị hỏng.

Cuối cùng, bạn nhận được \(1\) yên từ mỗi máy phát điện hoạt động. Tuy nhiên, bạn phải trả \(1\) yên chi phí sửa chữa cho mỗi máy phát điện bị hỏng. Lợi nhuận là tổng tiền nhận được trừ đi tổng chi phí sửa chữa.

Cho cách nối các trạm bằng dây dẫn và thông tin về vị trí các máy phát điện, hãy tính lợi nhuận lớn nhất mà bạn có thể đạt được.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\).
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), mô tả hai đầu của dây dẫn thứ \(i\).
• Dòng cuối chứa xâu \(S\) có độ dài \(N\), chỉ gồm các ký tự 0 và 1. Ký tự thứ \(i\) (\(1 \le i \le N\)) là 0 nếu trạm \(i\) không có máy phát điện, và là 1 nếu trạm đó có máy phát điện.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa lợi nhuận lớn nhất khi chọn một số máy phát điện và bật công tắc của tất cả các máy được chọn.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N-1\).
• \(1 \le B_i \le N\) với \(1 \le i \le N-1\).
• \(A_i \ne B_i\) với \(1 \le i \le N-1\).
• Có thể đi từ một trạm bất kỳ đến bất kỳ trạm nào khác bằng cách đi qua các dây dẫn.
• \(S\) có độ dài \(N\), chỉ gồm các ký tự 0 và 1.
• \(S\) chứa ít nhất một ký tự 1.

Phân nhóm

Mọi phân nhóm đều thỏa mãn toàn bộ ràng buộc ở trên.

1. 6 điểm: \(N \le 16\).
2. 41 điểm: \(N \le 2000\).
3. 53 điểm: Không có ràng buộc bổ sung.

Ví dụ

6
2 3
4 3
1 3
3 5
6 2
110011

3

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

3

16
7 10
5 11
9 4
14 12
2 11
14 16
4 2
1 13
11 3
7 1
15 9
2 1
11 6
14 9
8 9
0111111001001110

5

Nguồn

JOI Open Contest 2020, bài 3. Bản dịch từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản (JCIOI), theo giấy phép CC BY-SA 4.0.