{"code":"brvtdttinhlqd25p3","name":"Cắt cành (Bài 3 Chọn ĐT HSG Tỉnh THPT chuyên Lê Quý Đôn Vũng Tàu 2025)","description":"Sau một ngày làm việc vất vả, Phát sẽ thưởng cho mình bằng những bữa ăn với những trái ớt ngon lành. Anh ta có $n$ trái ớt được nối với nhau qua $n-1$ cành, hai trái ớt bất kì luôn được nối với nhau qua chuỗi những cành. Tóm lại, những trái ớt tạo thành cây. Phát sẽ có ba bữa ăn trong ngày. Để chuẩn bị cho bữa ăn, anh ta sẽ cắt $2$ cành cây bất kì để được $3$ đùm ớt, mỗi đùm cho một bữa.\r\n\r\n**Yêu cầu:** Phát muốn cắt sao cho độ chênh lệch giữa đùm có nhiều ớt nhất và ít nhất là nhỏ nhất. Bạn phải giúp anh ấy tìm độ chênh lệch đó.\r\n\r\n## Scoring\r\n\r\n- Subtask $1$ ($25\\%$ số điểm): $3 \\le n \\le 200$;\r\n- Subtask $2$ ($50\\%$ số điểm): $3 \\le n \\le 2000$;\r\n- Subtask $3$ ($100\\%$ số điểm): $3 \\le n \\le 200000$.\r\n\r\n## Input\r\n\r\nDữ liệu vào từ file **CHILLIS.INP**:\r\n\r\n- Dòng đầu chứa số nguyên $n$ là số lượng ớt. Các trái ớt được đánh số từ $1 \\rightarrow n$.\r\n- Mỗi dòng trong $n-1$ dòng còn lại gồm hai số nguyên $x$ và $y$ $\\left( 1 \\le x, y \\le n \\right)$ số hiệu của hai trái ớt nối trực tiếp với nhau.\r\n\r\n## Output\r\n\r\nKết quả ghi vào file **CHILLIS.OUT** độ chênh lệch tối thiểu giữa đám có nhiều ớt nhất và ít ớt nhất.\r\n\r\n## Example\r\n\r\n!!! example \"Test 1\"\r\n    ???  \"Input\"\r\n        4\r\n        1 2\r\n        2 3\r\n        3 4\r\n    ??? success \"Output\"\r\n        1\r\n    ??? warning \"Note\"\r\n        Có $3$ cách cắt để tạo thành $1$ đùm có $2$ trái ớt và $2$ đám có $1$ trái ớt. Do đó độ chênh lệch là $2 - 1 = 1$.\r\n        \r\n!!! example \"Test 2\"\r\n    ???  \"Input\"\r\n        9\r\n        1 3\r\n        2 3\r\n        3 4\r\n        3 5\r\n        5 6\r\n        5 7\r\n        7 8\r\n        7 9\r\n    ??? success \"Output\"\r\n        2\r\n    ??? warning \"Note\"\r\n        Số lượng trái ớt trong các đùm lần lượt là $4, 2, 3$ nên kết quả là $4 - 2 = 2$.","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}