Mô tả và yêu cầu

Truyền dữ liệu
TR là một hệ thống trao đổi dữ liệu trực tiếp giữa các máy
tính của người dùng. Lớp của Hiệp có 𝑁 bạn, mỗi bạn có một máy
tính sử dụng hệ thống TR và được kết nối với nhau theo đồ thị dạng
cây. Với tư cách là lớp trưởng, Hiệp sử dụng hệ thống này để gửi
bài tập đến tất cả các bạn trong lớp.
Hiệp sẽ là người chịu trách nhiệm nhận bài tập về nhà từ thầy
cô và chuyển tiếp đến các bạn trong lớp. Do hạn chế của hệ thống,
cứ mỗi một phút, mỗi máy tính trong mạng chỉ có thể gửi dữ liệu
đến duy nhất một máy khác được kết nối trực tiếp.
Đôi lúc, trong một số trường hợp cần phải hoàn thành việc
truyền tải nhanh hơn, thầy cô sẽ gửi bài tập cho cả Hiệp và bạn lớp
phó cùng một thời điểm.
Yêu cầu: Hãy tính thời gian tối thiểu để tất cả các bạn trong lớp nhận được bài tập.
Dữ liệu vào từ tệp văn bản TDL.INP:
 Dòng đầu tiên của đầu vào chứa số nguyên 𝑁 (1 ≤ 𝑁 ≤ 105) là số lượng máy tính.
 𝑁 − 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên khác nhau 𝑥 và 𝑦 (1 ≤ 𝑥, 𝑦 ≤ 𝑁)
mô tả nhãn của các máy tính được kết nối trực tiếp;
 Dòng tiếp theo chứa một số 𝑀 (1 ≤ 𝑀 ≤ 2) là số lượng bản copy bài tập về nhà thầy
cô gửi ban đầu;
 Dòng tiếp theo chứa 𝑀 số nguyên dương mô tả nhãn của máy tính lần lượt của Hiệp và
lớp phó học tập.
Kết quả ghi ra tệp văn bản TDL.OUT: Gồm một số nguyên là thời gian tối thiểu hoàn thành
công việc.
TDL.INP TDL.OUT Giải thích
6 3 Ban đầu Hiệp nhận được bài tập.
1 2 Phút thứ 1: máy tính có nhãn 2 nhận được bài tập;
2 3 Phút thứ 2: máy tính có nhãn 3 và 5 nhận được bài tập;
2 4 Phút thứ 3: máy tính có nhãn 4 và 6 nhận được bài tập;
1 5
5 6
1
1
6 2 Ban đầu Hiệp và lớp phó nhận được bài tập.
1 2 Phút thứ 1: máy tính có nhãn 3 và 5 nhận được bài tập;
2 3 Phút thứ 2: máy tính có nhãn 4 và 6 nhận được bài tập;
2 4
1 5
5 6
2
1 2

Giới hạn và chấm điểm

 Có 25% số test ứng với 25% số điểm có 𝑁 ≤ 20;
 25% số test khác ứng với 25% số điểm có 𝑀 = 1;
 25% số test khác ứng với 25% số điểm có 𝑀 = 2; 𝑁 ≤ 1000;
 25% số test còn lại ứng với 25% số điểm không có ràng buộc gì thêm.