Canada là một quốc gia rộng lớn, nhưng nhiều vùng không có người ở và phần lớn dân cư sống gần biên giới phía nam. Đường cao tốc xuyên Canada, hoàn thành năm 1962, nối St. John's ở phía đông với Victoria ở phía tây, dài 7821 km.

Người Canada yêu thích khúc côn cầu. Sau một trận đấu, hàng nghìn người hâm mộ lái xe về nhà, gây ùn tắc nghiêm trọng. Một doanh nhân giàu có muốn mua một đội khúc côn cầu và xây sân đấu mới. Hãy giúp ông chọn vị trí sân đấu để giảm ùn tắc sau trận đấu.

Các thành phố được nối bởi mạng lưới đường hai chiều. Giữa mỗi cặp thành phố có đúng một tuyến đường. Tuyến đường từ thành phố \(c_0\) đến \(c_k\) là một dãy các thành phố phân biệt \(c_0,\ldots,c_k\), trong đó có đường nối \(c_{i-1}\) với \(c_i\) với mọi \(1\le i\le k\).

Sân đấu phải được xây trong một thành phố. Sau trận đấu, mọi người hâm mộ đi từ thành phố có sân đấu về thành phố mình sinh sống, ngoại trừ những người đã sống tại thành phố có sân đấu. Mức ùn tắc trên một con đường tỷ lệ với số người đi qua đường đó. Hãy chọn thành phố sao cho mức ùn tắc trên con đường đông nhất nhỏ nhất có thể. Nếu có nhiều thành phố tốt như nhau, được chọn bất kỳ thành phố nào trong số đó.

Yêu cầu cài đặt

int LocateCentre(int N, int P[], int S[], int D[]);

N là số thành phố, được đánh số từ 0 đến N-1. Mảng P gồm N số nguyên dương; P[i] là số người hâm mộ sống tại thành phố i. Hai mảng S và D có N-1 phần tử: đường thứ i nối S[i] với D[i]. Hàm trả về số hiệu thành phố được chọn để xây sân đấu. Không viết main.

Dữ liệu vào

Lời giải nhận dữ liệu qua các tham số của LocateCentre, không đọc đầu vào chuẩn. Trình chấm mẫu đọc N ở dòng đầu; N dòng tiếp theo chứa P[0] đến P[N-1]; N-1 dòng cuối chứa các cặp S[i] D[i].

Dữ liệu ra

Trả về số hiệu thành phố tối ưu; không in kết quả. Trình chấm mẫu sẽ in giá trị trả về.

Ràng buộc

\(1\le N\le 1\,000\,000\); \(P[i]\ge1\); tổng số người hâm mộ không vượt quá \(2\,000\,000\,000\). Có đúng \(N-1\) đường hai chiều và đúng một tuyến đường giữa hai thành phố bất kỳ. Các đầu mút nằm trong khoảng từ 0 đến \(N-1\).

Phân nhóm

Mỗi nhóm chỉ có điểm khi vượt qua toàn bộ các bộ kiểm tra của nhóm. Có thể có lời giải vượt qua nhóm 3 nhưng không vượt qua nhóm 2. Trong kỳ thi gốc, điểm của toàn bài được quyết định bởi một bài nộp duy nhất.

Ví dụ

5
10
10
10
20
20
0 2
1 2
3 2
4 3

3

Chi tiết triển khai

Gói LQDOJ nhận một tệp C++ dùng traffic.h; tải templates.zip để lấy giao diện và mã khung. Đề gốc hỗ trợ traffic.c, traffic.cpp hoặc traffic.pas, giao diện traffic.h hoặc traffic.pas, không có hàm gọi ngược từ trình chấm. Thư mục làm bài gốc là /home/ioi2010-contestant/traffic/; các trình chấm mẫu là grader.c, grader.cpp, grader.pas, với đầu vào grader.in.* và kết quả grader.expect.*. Lệnh runc/submit cùng phím Control-R/Control-J thuộc môi trường thi gốc; trên LQDOJ, nộp tệp cài đặt hàm.

Nguồn

IOI 2010, ngày 2, bài 2 — Traffic Congestion. Đề chính thức, PDF tiếng Anh.