Bò Trốn (Platinum)

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Cho một cây gồm $N$ đỉnh và $N - 1$ cạnh. Các đỉnh bậc 1 (chỉ có đúng một cạnh kề) gọi là lá. Ban đầu, một con bò xuất hiện tại đỉnh $u$ và bắt đầu di chuyển trên cây. Các nông dân đặt tại các lá và sẽ di chuyển để chặn bắt bò; tất cả đều di chuyển với tốc độ bằng nhau, các nông dân biết vị trí của bò và bò cũng biết vị trí các nông dân.

Một nông dân bắt được bò khi ở cùng đỉnh với bò. Các nông dân chỉ cần chặn bò — tức là di chuyển đến các lá sao cho dù bò đi theo hướng nào, luôn có một nông dân chắn trước. Bò bị bắt nếu mọi đường đi từ vị trí của bò đến lá đều bị chặn.

Với mỗi đỉnh $u$ ( $1 \leq u \leq N$ ), hãy tính số nông dân tối thiểu cần thiết để đảm bảo bắt được bò nếu bò xuất hiện tại đỉnh $u$ (cả hai bên đều chơi tối ưu).

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ .
$N - 1$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ , $b$ mô tả một cạnh giữa đỉnh $a$ và đỉnh $b$ .

Dữ liệu ra

In $N$ dòng, dòng thứ $i$ là số nông dân tối thiểu cần thiết khi bò xuất hiện tại đỉnh $i$ .

Ràng buộc

$2 \leq N \leq 7 \times 10^{4}$

Ví dụ

Input	Output	Giải thích
7 1 2 1 3 3 4 3 5 4 6 5 7	3 1 3 3 3 1 1	Cây có 7 đỉnh. Các lá là: 2, 6, 7. Nếu bò ở đỉnh 1 cần 3 nông dân; nếu bò ở lá (2, 6, 7) chỉ cần 1 nông dân.
5 1 2 1 3 2 4 2 5	2 3 1 1 1	Cây có nhánh. Lá là: 3, 4, 5. Nếu bò ở đỉnh 1 cần 2 nông dân; nếu bò ở đỉnh 2 cần 3 nông dân; lá chỉ cần 1.

Ghi chú

Nếu bò xuất hiện tại một lá, chỉ cần 1 nông dân tại chính lá đó là đủ. Với các đỉnh nội tuyến, số nông dân bằng số lá "nằm gần lá hơn hoặc bằng" so với đỉnh đó.

Bình luận

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