If you prefer easier problem, please visit here
思考题 for dw
Childish War (Hard)
Miss. Broken Tail(Wei Duan) is the Math teacher of NFLS Class 8 Junior 3.She is a kind teacher.
Miss. East(Fang Dong) is the Math teacher of NFLS Class 4 Junior 3.She is a kind teacher too.
Tail loves walking around the Xuanwu Lake to relax. So does East.
There are N islands numbered from 1 to N on Xuanwu Lake and there are M bidirectional weighted edges connecting them. It is made sure that the islands are connected and no edge has negative weight.
Tail is located at island S and East is located at island T. They decided to play a childish game.
The game has Q rounds, in each round East chooses an positive integer R and draw a circle centered at her position with the radius R1.
Tail will choose an radius R2 and draw a circle centered at her position with R2 as radius too. The score of Tail will be calculated as follows:
Let's call the number of islands included in Tail's circle but not in East's circle
For each query, find the max score of Tail's circle.
S=1 T=3 a=3 b=1
Q1:Tail can draw a circle of radius 3 so that X=3(1,2,4) Y=1(3).
Q2:Tail can draw a circle of radius 4 so that X=0 Y=4(1,2,3,4).