#892. OVERPART - Quá nửa

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Thành phố HP xinh đẹp có n địa điểm được nối với nhau bởi n-1 con đường hai chiều đảm bảo bất kỳ hai địa điểm nào cũng đến được nhau thông qua các các con đường này.

Thành phố HP dự định xây công viên giải trí ở 1 trong n địa điểm, tuy nhiên theo chủ trương “của dân, do dân và vì dân” nên các nhà lãnh đạo quyết định hỏi ý kiến của mọi người. Những người dân ở địa điểm i mong muốn công viên giải trí được xây dựng ở địa điểm a_i .

Các nhà lãnh đạo của thành phố HP đã cử ra m phóng viên uy tín đi hỏi, phóng viên thứ i sẽ xuất phát từ địa điểm u_i , đi đến địa điểm v_i theo con đường ngắn nhất và sẽ hỏi một người dân bất kỳ (vì mọi người dân ở địa điểm đó đều có câu trả lời như nhau) ở mỗi địa điểm đi qua (tính cả u_i v_i ). Sau khi hỏi xong, phóng viên đó sẽ báo cáo ra địa điểm mà có quá nửa số người dân mà phóng viên đã hỏi mong muốn xây dựng công viên giải trí. Nếu không tìm được địa điểm như vậy thì phóng viên đó sẽ không báo cáo.

Yêu cầu: Với mỗi phóng viên bạn cần đưa ra báo cáo của phóng viên đó hoặc in ra -1 nếu phóng viên đó không tìm được địa điểm thỏa mãn.

Dữ liệu:

  • Dòng đầu tiên chứa số nguyên n\ (1≤n≤50000) là số địa điểm;
  • Dòng tiếp theo chứa n số nguyên, số thứ i a_i\ (1≤a_i≤n) ;
  • Dòng thứ i trong n-1 dòng tiếp theo chứa hai số nguyên u_i,v_i\ (1≤u_i,v_i≤n) mô tả một con đường nối hai địa điểm u_i v_i ;
  • Dòng tiếp theo chứa số nguyên m\ (1≤m≤100000) là số phóng viên;
  • Dòng thứ i trong m dòng tiếp theo chứa hai số nguyên u_i,v_i\ (1≤u_i,v_i≤n) mô tả con đường phóng viên thứ i đi.

Kết quả:

  • Ghi ra m dòng, dòng thứ i là báo cáo của phóng viên i hoặc in ra –1 nếu phóng viên đó không tìm được địa điểm thỏa mãn.

Ví dụ:

Dữ liệu:

6 
1 1 1 2 2 2
1 2
1 3
2 4
2 5
3 6
3
4 2
4 5
4 6

Kết quả:

-1
2
1

Giải thích:

  • Các giá trị hỏi được của phòng viên đầu tiên theo thứ tự là: \{2,1\} , không có giá trị nào xuất hiện quá nửa;
  • Các giá trị hỏi được của phòng viên thứ hai theo thứ tự là: \{2,1,2\} , giá trị 2 xuất hiện 2 lần;
  • Các giá trị hỏi được của phòng viên thứ ba theo thứ tự là: \{2,1,1,1,2\} , giá trị 1 xuất hiện 3 lần.

Ràng buộc:

  • 25\% số test ứng với 25\% số điểm của bài thỏa mãn điều kiện n,m≤5000 ;
  • 25\% số test khác ứng với 25\% số điểm của bài thỏa mãn điều kiện n≤5000 ;
  • 25\% số test khác ứng với 25\% số điểm của bài thỏa mãn điều kiện địa điểm i chỉ có đường nối trực tiếp đến i-1 i+1\ (1< i < n) ;
  • 25\% số test còn lại ứng với 25\% số điểm của bài không có điều kiện gì thêm.