123Code...

Nội dung Bài tập

Mã:: BUSINESS

Tên:: Kinh doanh trà sữa

Dạng thi:: oi

Thang điểm:: 6 điểm

Giới hạn thời gian:: 1 giây

Giới hạn bộ nhớ:: 256 MB

Nguồn bài tập:: VNOI Online 2018

Được tạo bởi:: phuc

: Share

BUSINESS.INP	BUSINESS.OUT
7 2 5 4 1 2 1 3 1 5 3 4 2 6 2 7	1

Đất nước VNOI có N thành phố được đánh số từ 1 đến N . Có N - 1 con đường hai chiều, con đường thứ i nối liền hai thành phố u_i và v_i . Một đường đi từ s đến t là một dãy các thành phố s, v₁ , v₂,…, v_k, t sao cho hai thành phố liên tiếp trong dãy đều được nối bởi một con đường nào đó, và độ dài của đường đi đó là k + 1. Khoảng cách giữa hai thành phố u và v là độ dài của đường đi ngắn nhất từ u đến v. Dữ liệu vào đảm bảo giữa hai thành phố bất kì đều có đường đi đến nhau. Tập đoàn kinh doanh trà sữa PVH đã mở K chi nhánh, chi nhánh thứ i nằm ở thành phố p_i. Không có hai chi nhánh nào nằm ở cùng một thành phố. Do nhu cầu uống trà sữa tăng cao của giới trẻ VNOI hiện nay, anh Hạnh, CEO tập đoàn PVH, quyết định mở thêm đúng một chi nhánh nữa (hiển nhiên là ở một thành phố nào đó chưa có chi nhánh). Anh Hạnh mong muốn rằng khoảng cách lớn nhất từ một thành phố bất kì đến một chi nhánh là nhỏ nhất. Nói cách khác, gọi d u là khoảng cách nhỏ nhất từ thành phố u đến một thành phố có chi nhánh, gọi S = max( d u ) ( u = 1, ..., N ). Anh Hạnh mong muốn mở thêm một chi nhánh sao cho giá trị của S là nhỏ nhất. Anh Hạnh sẽ tặng 10 ly trà sữa cho bất cứ ai giúp anh giải quyết bài toán này. Hãy giúp anh Hạnh để được uống trà sữa miễn phí nào! Dữ liệu ● Dòng đầu tiên chứa số hai số nguyên N và K, lần lượt là số thành phố trong đất nước VNOI và số chi nhánh của tập đoàn PVH (1 ≤ N ≤ 300000, 0 ≤ K ≤ N - 1). ● Dòng tiếp theo chứa K số nguyên p₁ , p₂ , ..., p_K (1 ≤ p_i ≤ N) , là các thành phố được mở chi nhánh. ● N - 1 dòng tiếp theo, dòng thứ i gồm hai số nguyên u i và v i (1 ≤ u_i , v_i ≤ N) , là hai thành phố được nối bởi con đường thứ i . Kết quả ● In ra giá trị nhỏ nhất của S sau khi tập đoàn PVH mở thêm một chi nhánh. Ví dụ: BUSINESS.INP BUSINESS.OUT 7 2 5 4 1 2 1 3 1 5 3 4 2 6 2 7 1 Giải thích ví dụ: Chọn thành phố 2 để mở thêm chi nhánh. Chấm điểm ● Subtask 1 (20% số điểm): 1 ≤ N ≤ 3000; ● Subtask 2 (20% số điểm): 1 ≤ N ≤ 300000, K = 0; ● Subtask 3 (30% số điểm): 1 ≤ N ≤ 300000, K ≤ 10; ● Subtask 4 (30% số điểm): không có ràng buộc gì thêm
Quảng cáo