Chỉ số hạnh phúc

Điểm: 6,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Một đất nước có $n$ thành phố và $n - 1$ con đường vô hướng nối các cặp thành phố, tạo thành một cây. Các thành phố được đánh số từ $1$ đến $n$ , trong đó thành phố $1$ là thủ đô.

Đất nước có $m$ cư dân. Thành phố $i$ có $p_{i}$ người sinh sống, nhưng tất cả đều làm việc tại thủ đô. Buổi tối, mỗi người trở về nhà theo đường đi ngắn nhất trên cây.

Mỗi người khi rời thủ đô có thể đang ở tâm trạng tốt hoặc tâm trạng xấu. Trên đường về, tâm trạng có thể chuyển từ tốt sang xấu, nhưng không bao giờ chuyển từ xấu sang tốt. Tâm trạng không thay đổi bên trong một thành phố.

Tại mỗi thành phố có một thiết bị đo tâm trạng. Thiết bị tại thành phố $i$ tính chỉ số hạnh phúc $h_{i}$ bằng:

$h_{i} = (số người tâm trạng tốt đi qua thành phố i) - (số người tâm trạng xấu đi qua thành phố i) .$

Cho dữ liệu $p_{i}$ và $h_{i}$ , hãy kiểm tra xem có tồn tại một cách phân bố tâm trạng ban đầu (tại thủ đô) và các thời điểm chuyển tâm trạng dọc đường sao cho tất cả các chỉ số $h_{i}$ khớp chính xác hay không.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ test.
Mỗi bộ test:
- Dòng đầu chứa hai số nguyên $n$ và $m$ — số thành phố và số cư dân.
- Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ ( $0 \leq p_{i} \leq m$ , $p_{1} + p_{2} + \dots + p_{n} = m$ ).
- Dòng thứ ba chứa $n$ số nguyên $h_{1}, h_{2}, \dots, h_{n}$ ( $- 10^{9} \leq h_{i} \leq 10^{9}$ ).
- $n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ , $y_{i}$ mô tả một con đường.

Dữ liệu ra

Với mỗi bộ test, in ra YES nếu dữ liệu thu được là hợp lệ, ngược lại in NO.

Ràng buộc

$1 \leq t \leq 10 000$
$1 \leq n \leq 10^{5}$
$0 \leq m \leq 10^{9}$
$1 \leq x_{i}, y_{i} \leq n$ , $x_{i} \neq y_{i}$
Tổng $n$ trên tất cả các bộ test không vượt quá $2 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
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	NO NO	Cả hai trường hợp đều không tồn tại phân bố tâm trạng phù hợp với $h_{i}$ đã cho.
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	YES YES	Ở bộ thứ nhất: cả 4 người rời thủ đô đều vui vẻ, một số chuyển sang tâm trạng xấu trước khi đến thành phố $4$ và thành phố $6$ . Ở bộ thứ hai: cả 11 người đều rời thủ đô trong tâm trạng xấu.

Bình luận

Không có bình luận tại thời điểm này.