Tập Hợp Đàn Bò

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò kết nối với nhau qua $N - 1$ cặp bạn bè tạo thành cây (mọi bò đều kết nối với nhau qua chuỗi bạn bè). Các bò phải rời đi lần lượt từng con theo quy tắc: chừng nào còn ít nhất hai con bò, mỗi con còn lại phải có ít nhất một bạn cũng còn lại (tức là bò rời đi phải là lá của cây con còn lại).

Ngoài ra có $M$ ràng buộc thứ tự: mỗi ràng buộc $(a_{i}, b_{i})$ yêu cầu bò $a_{i}$ phải rời đi trước bò $b_{i}$ .

Với mỗi con bò $i$ từ $1$ đến $N$ , hãy xác định: liệu bò $i$ có thể là con cuối cùng rời đi (thỏa mãn tất cả ràng buộc) hay không?

Dữ liệu vào

Dòng 1: hai số nguyên $N$ và $M$ ( $1 \leq N, M \leq 10^{5}$ )
$N - 1$ dòng tiếp theo: mỗi dòng hai số nguyên $x_{i}, y_{i}$ — cặp bạn bè (cạnh của cây)
$M$ dòng tiếp theo: mỗi dòng hai số nguyên $a_{i}, b_{i}$ — bò $a_{i}$ phải rời trước bò $b_{i}$

Dữ liệu ra

$N$ dòng, dòng $i$ chứa $1$ nếu bò $i$ có thể là con cuối cùng, ngược lại chứa $0$ .

Ràng buộc

$1 \leq N, M \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 1 2 2 3 3 4 4 5 2 4	0 0 1 1 1	Cây là đường thẳng 1-2-3-4-5, ràng buộc: 2 trước 4. Bò 3, 4, 5 có thể là cuối: ví dụ thứ tự hợp lệ khi bò 5 cuối: 1→2→4→3→5 (2 trước 4 ✓). Bò 1 và 2 không thể vì bò 2 có ràng buộc đi trước bò 4.

Bình luận

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