Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KTREEC - Bán hàng

Quả là trái dừa đã cho Pirate một ý tưởng thiên tài khi chuyển sang bán cocktail. Bây giờ Pirate đã mở rộng mạng lưới của mình sang khắp các hòn đảo bên cạnh. Tại mỗi hòn đảo, anh mở một cửa hàng cocktail. Tùy theo sản vật của từng hòn đảo mà mỗi cửa hàng chuyên về một loại cocktail nhất định. Tuy nhiên, do hệ thống đường nối các hòn đảo với nhau vẫn chưa được cải thiện (vẫn dùng các cây cầu dừa để vừa đủ cho từ mỗi hòn đảo chỉ có một đường đi duy nhất đến mọi hòn đảo khác) nên khi giao hàng cho khách gặp một vấn đề nho nhỏ: nhiều khi khách  hàng lại không muốn thưởng thức sản phẩm trên hòn đảo của mình mà lại muốn dùng những loại cocktail khác. Để tiết kiệm chi phí đi lại, Pirate phải chọn cửa hàng cung ứng loại cocktail tương ứng gần với hòn đảo của người khách nhất để đi giao hàng...

 

Input

  • Dòng thứ nhất: ghi số nguyên N - số hòn đảo.
  • N - 1 dòng tiếp theo: mỗi dòng ghi hai số nguyên x và y - có một cây cầu dừa nối hai hòn đảo x và y.
  • Dòng thứ N + 1: ghi số nguyên C - số loại cocktail mà các cửa hàng cung ứng.
  • Dòng thứ N + 2: ghi N số nguyên - loại cocktail chuyên biệt của từng hòn đảo.
  • Dòng thứ N + 3: ghi số nguyên M - số các vị khách.
  • M dòng tiếp theo: mỗi dòng mô tả hai số nguyên x và y - người khách ở đảo x yêu cầu cocktail loại y.

Output

  • Gồm M dòng, mỗi dòng ghi ra khoảng cách (tính bằng số cây cầu dừa) cửa hàng gần nhất phải đi để giao hàng cho người khách tương ứng.

Giới hạn:

  • Trong mỗi test, 1 ≤ C ≤ N ≤ 104, 1 ≤ M ≤ 104.
  • 60% số test có 1 ≤ C ≤ 102.

Example

Input:
8
1 2
1 3
2 7
2 8
3 4
4 5
4 6
4
1 2 4 2 3 1 3 2
8
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4

Output: 1
2
0
1
2
2
3
3

Giải thích: Chỉ có cửa hàng 3 chuyên về loại cocktail 4, nên kết quả chính là khoảng cách từ hòn đảo 3 đến các hòn đảo còn lại.


Được gửi lên bởi:Nguyễn Xuân Khánh
Ngày:2011-07-10
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2019-11-09 09:09:39
Cảm ơn mọi người ạ, bài thật là thâm!
2018-09-03 16:26:29
centroid decomposition O(NlgN) Mem=10^8bytes :v
2018-01-20 02:27:43
> sqrt thi bfs con khong thi LCA
2015-05-11 18:14:48 Phong
làm mãi mà vẫn 93.75. K hiểu tại sao @@ Ai biết chỉ với @@
2014-06-23 11:13:47 Anh Duc Le
Thuật bựa O(N * C) vẫn 1 đấm AC :v
2014-06-11 10:17:49 Lihn
bị 43.75 là sai ở đâu vậy ???
2012-08-19 13:35:11 Ðỗ Quốc Vương
97.35 :((
Làm sao để khỏi TLE test cuối vậy mấy anh?
2012-07-29 15:47:26 Vi Tiểu Bảo
hay

Last edit: 2012-07-29 15:50:05
2011-09-04 14:12:55 St.VDQD
không hiểu sao mình chỉ 93.75
2011-07-21 04:16:00 Nguyễn Xuân Khánh
@...???!!!: tle test cuoi :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.