Chủ trương sáp nhập các đơn vị hành chính cấp tỉnh được thực hiện nhằm mục tiêu tinh giản bộ máy, tiết kiệm ngân sách, tạo không gian phát triển rộng hơn, từ đó tập trung nguồn lực và trí tuệ để phát triển kinh tế – xã hội bền vững.
Giả sử cả nước hiện có N tỉnh, trong đó tỉnh thứ i có diện tích là S_i (tính theo km^2). Chính phủ đưa ra kế hoạch có K cặp tỉnh sẽ được sáp nhập bắt buộc; biết rằng mỗi cặp (u,v) là tỉnh u và tỉnh v sẽ hợp nhất thành một tỉnh mới.
Nếu một tỉnh xuất hiện trong nhiều cặp (ví dụ: 1-2, 2-3), thì tất cả các tỉnh liên quan (1, 2, 3) sẽ gộp thành một tỉnh duy nhất có diện tích bằng tổng diện tích của các tỉnh ban đầu.
Yêu cầu: Hãy xác định tỉnh có diện tích lớn nhất sau khi thực hiện xong toàn bộ K lần sáp nhập,
