TLEoj Contest #05 - Villa - TLEOJ: TLE Online Judge

TLEoj Contest #05 - Villa

Điểm: 1500 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

HoBaoPhuc2009

Dạng bài

Hẳn chúng ta ai cũng biết hành trình từ đáy xã hội đi lên của idol tên Đ nào đó. Ngày hôm nay, gia đình của anh ấy - gia đình Villa, đã đón tiếp 1 thành viên mới, đó chính là _nhphuc. Để chào mừng thành viên mới và gắn kết gia đình, Đ quyết định cho cả gia đình thực hiện hành trình đi lên đỉnh xã hội trên một cây có $n$ đỉnh và $n–1$ cạnh. Đỉnh $1$ của cây tượng trưng cho cánh cổng dẫn tới đỉnh xã hội và các đỉnh lá dưới cùng của cây tượng trưng cho ngôi nhà của Mân đàn, Vozer,…. (đứng đầu là HoBaoPhuc2009). Cụ thể, trong một đơn vị thời gian, mỗi thành viên của gia đình sẽ đi tới đỉnh cha mà đỉnh họ đang đứng cho tới khi tới được đỉnh $1$ và sau đó thoát khỏi cây.

Nhưng con đường lên tới đỉnh xã hội không dễ dàng như vậy, mỗi đỉnh trên cây không thể chứa hai thành viên của gia đình cùng một lúc, vì vậy tổng lãnh tên Đ đã đưa ra một phương án đó chính là: Với mỗi “đáy” mà một thành viên đứng ban đầu, thành viên đó có thể chèn thêm một đỉnh con khác cho đỉnh đó, sau đó chuyển sang đứng ở “đáy” mới này.

Các thành viên của gia đình tuy không muốn bị “ùn tắc giao thông” khi lên đỉnh xã hội nhưng cũng muốn số lần “đáy” mới được thêm vào là ít nhất, hãy giúp họ tính toán nhé.

Input, Output và Subtasks

Input

Dòng đầu tiên chứa số nguyên dương $n\ (n\le 10^5)$
$n - 1$ dòng tiếp theo chứa hai số nguyên dương $u,v\ (1\le u,v\le n)$ biểu thị có đường đi nối giữa hai đỉnh $u$ và $v$ .

Output

Một dòng duy nhất gồm số lần kéo đáy ít nhất cần thực hiện

Sample 1

Input

Output

Note

Chúng ta có thể thấy trong lần di chuyển đầu (đơn vị thời gian đầu tiên) thành viên ở đỉnh $2$ sẽ di chuyển tới đỉnh $1$ còn thành viên ở đỉnh $4$ và $5$ sẽ gặp ùn tắc ở đỉnh $3$ . (minh họa cây ở hình ảnh 1)

Vì vậy, thành viên ở vị trí $5$ sẽ kéo dài đáy của họ (mịnh họa cây ở hình ảnh 2). Sau đó cây thỏa mãn với đường đi của mỗi thành viên là:
$2\rightarrow 1$ -> đỉnh xã hội
$4\rightarrow 3\rightarrow 1$ -> đỉnh xã hội
$6\rightarrow 5\rightarrow 3\rightarrow 1$ -> đỉnh xã hội
Có thể thấy trong cùng một đơn vị thời gian không có 2 thành viên nào ở cùng vị trí với nhau.

Bình luận

Không có bình luận nào.