Solved!
Difficulty: Div2E-Div2F

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 R1 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 X.Let's call the number of islands included in Tail's circle and in East's circle Y. Then the score of Tail's circle is aX+bY where a and b are given.
For each query, find the max score of Tail's circle.

Example

Input
graph={
[1,2,2],
[2,3,2],
[1,4,2],
[4,3,2],
[1,3,3],
}
S=1 T=3 a=3 b=1
Query={
[1],
[4]
}
Output
10
4
Explain
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).

Constraints

Subtask 1(50%):0<=a,b<=1e9,1<=N,M,Q<=1e5
Subtask 2(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=1000
Subtask 3(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=100000

Solution

By XGN:

For subtask 1, If a,b\geq 0, it's easy to find out that Tail can simply choose R_2=\infin using greedy.

Generally, first we need to work out the distances of an island i to S and T. Let's call them d_{Si} and d_{Ti}. This can be done by Dijkstra in O(m\log m).

We first group the islands by their distance d_{Si}. Islands with the same d_{Si} belong to the same group.
We also give each island a value called contribution, which represents how many points can be earned if this island is included in Tail's circle. We also define the contribution of a group to be the sum of contribution of each island in the group. Normally, without East's disturbance, each island's contribution is always a. If we sort the groups in the order of d_S from small to big, we will realize that the answer is the maximum prefix sum of contributions of groups.

Next we will consider East's influence. If an island is "conquered" by East, its contribution will change from a to b.

So we will do the problem offline. Let's sort R_1 from small to big. Then in each query, some islands are added to East's territory. We update those islands' contribution one by one and after each chunk of contribution is updated, we query the maximum prefix sum. The update process is done at most n times. Thus we can use Segment Tree to process the queries and solve the problem.

Time Complexity: O(m\log m+Q\log n)