Submit solution

Points: 150.00 (partial)
Time limit: 1.0s
Memory limit: 1024M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Có n thành phố và n-1 con đường 2 chiều nối trực tiếp 2 thành phố với nhau. Người ở một thành phố bất kì đều có thể đến thành phố khác thông qua n-1 con đường này. Các thành phố được đánh số từ 1 đến n và thành phố 1 là thủ đô. Nói cách khác, quốc gia có cấu trúc dạng cây.

Có m công dân sống ở n thành phố. Có pi công dân sinh sống tại thành phố i nhưng tất cả bọn họ đang làm việc tại thủ đô. Đến tối, các công dân quay về thành phố của mình bằng con đường ngắn nhất.

Mỗi người có một tâm trạng khác nhau. Một vài người quay về trong tâm trạng tốt, số còn lại quay về trong tâm trạng xấu. Hơn nữa, một người cũng có thể phá hủy tâm trạng của chính mình trên đường về thành phố. Nếu một người đang trong tâm trạng xấu, anh ta sẽ không thể cải thiện được nó. Mỗi thành phố có một chỉ số hạnh phúc hi, được tính bằng cách lấy số người đến thành phố trong tâm trạng tốt trừ đi số người đến thành phố trong tâm trạng xấu. Mỗi thành phố được lắp đặt một cỗ máy hiện đại, cho biết tâm trạng của mỗi người đến thành phố. Một người sẽ không thay đổi tâm trạng của mình trong thành phố.

Cỗ máy này vẫn đang trong giai đoạn phát triển vì vậy sẽ có khả năng xảy ra sai sót khi đánh giá tâm trạng của một người. Vào một buổi đêm muộn, khi mọi công dân đã về nhà, chính phủ đã mời thầy Phú, nhà lập trình bậc nhất đến để kiểm tra các cỗ máy. Nhận thấy yêu cầu này quá đễ dàng, thầy Phũ đã nhường nó cho những lập trình viên trẻ tuổi để thử sức và tích lũy thêm kinh nghiệm. Liệu bạn có hoàn thành được yêu cầu này không?

Dữ liệu vào gồm:

  • Dòng đầu tiên là số t ( 1 <= t <= ~10^4~ ) - số bộ test.
  • Dòng đầu tiên của mỗi bộ test là hai số nguyên n,m ( 1 <= n <= ~10^5~, 0 <= m <= ~10^9~ ) - số thành phố và số công dân.
  • Dòng thứ hai là n số nguyên ~p_1~, ~p_2~ , ~p_3~,..., ~p_n~ (0 <= ~p_i~ <= m, ~p_1~ + ~p_2~ +... + ~p_n~ = m), trong đó pi là số người sống ở thành phố i.
  • Dòng thứ ba chứa n số nguyên h1, h2, h3,.., hn (-~10^9~ <= ~h_i~ <= ~10^9~), trong đó hi là chỉ số hạnh phúc của thành phố i.

Trong n-1 dòng tiếp theo, mỗi dòng chứa hai số nguyên phân biệt ~x_i~, ~y_i~ ( 1 <= ~x_i~, ~y_i~ <= n ) miêu tả đường nối giữa thành phố ~x_i~ và thành phố ~y_i~.. Có thể đảm bào rằng tổng của tất cả số n trong t bộ test không quá 2.~10^5~.

Kết qủa: Ghi ra với mỗi bộ test, in ra YES nếu như dữ liệu thu thập được là chính xác. Ngược lại in ra NO.

Ví dụ:
INPUT 1
2
7 4
1 0 1 1 0 1 0
4 0 0 -1 0 -1 0
1 2
1 3
1 4
3 5
3 6
3 7
5 11
1 2 5 2 1
-11 -2 -6 -2 -1
1 2
1 3
1 4
3 5
OUTPUT 1
YES
YES
INPUT 2
2
4 4
1 1 1 1
4 1 -3 -1
1 2
1 3
1 4
3 13
3 3 7
13 1 4
1 2
1 3
OUTPUT 2
NO
NO

Comments

Please read the guidelines before commenting.


There are no comments at the moment.