Điểm Xa Nhất Trên Cây · canuc80k3301

Có $n$ trạm và $n - 1$ tuyến nối hai chiều. Hệ thống liên thông và không có chu trình, vì vậy đường đi giữa hai trạm là duy nhất. Khoảng cách giữa hai trạm là số tuyến trên đường đi đó.

Với từng trạm $u$ , hãy xác định khoảng cách lớn nhất từ $u$ đến một trạm bất kỳ trong hệ thống.

Input

Dòng đầu chứa số nguyên $n$ .
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ , biểu diễn một tuyến nối hai chiều.

Output

In $n$ số nguyên trên một dòng. Số thứ $u$ là khoảng cách lớn nhất từ trạm $u$ đến một trạm trong cây.

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq u, v \leq n$ và $u \neq = v$ .
Các tuyến nối tạo thành một cây.
Mỗi giới hạn trên áp dụng cho một test độc lập.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 15$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

3 2 3 2 3

Giải thích: Từ trạm $2$ , trạm xa nhất là $5$ ở khoảng cách $2$ ; từ trạm $1$ , trạm $5$ cách $3$ tuyến. Xét tương tự cho các trạm khác thu được dãy kết quả.

Phân tích: Gốc hóa cây tại 1. down[u] là khoảng cách xa nhất từ u đi vào cây con; up[u] là khoảng cách xa nhất đi ra ngoài cây con. Đáp án là giá trị lớn hơn trong hai trạng thái này.
Thuật toán: Quét hậu thứ tự để tính down. Khi xử lý một đỉnh, lưu hai giá trị lớn nhất down[v]+1 của các con. Với con v, trạng thái từ phía cha bằng một cộng với maximum của up[u], đỉnh u và nhánh con tốt nhất khác v.
Chứng minh: Mọi đường từ u đến một đỉnh khác hoặc bắt đầu bằng cạnh xuống một con, hoặc bắt đầu bằng cạnh lên cha. down tối ưu nhóm thứ nhất. Khi truyền cho v, ba nguồn còn lại là chính u, phía trên u và các cây con anh em; việc loại nhánh v khiến chúng không chồng lặp với cây con của v. Do đó maximum của down[v] và up[v] xét đủ mọi đỉnh và là đáp án.
Độ phức tạp: Thời gian O(n), bộ nhớ O(n).