Orange Boy Can You Solve It Out? Ep.7

unsolvable 思考题 for unsolvable monkey

Dragon Bone Reborn

As a dragon yourself, it is very hard for you to live for every day there're a lot of knights who want to kill you and your bones are frequently broken.
Your bone system can be seen as a undirected tree T with N nodes and M edges. Each edge represents a bone and on each node there is a "repairer" who can repair your bone.
A process of repairing goes as follows:
Assume that the bone connecting (x,y) is broken, you firstly call some of the repairers to rush to node x or y.Note that the repairer cannot pass the broken bone. The time cost of this process is the maximum distance for each repairer to come.
Then they will start repairing after everyone is here. Assume that the "seriousness" of the injury is W and S repairers have come, then the time for this process is W/S rounding up
So the total repairing process time cost is the sum of the two subprocesses.
Now given M situations, in each situation you know what bone is broken and the seriousness. For each situation,print the minimal time needed to repair it.

Example Input

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

Example Output


Example Explain

For query 1, if we choose {2,4} then cost is 0+5/2=3
if we choose {2,4,1,3,6} then cost is 1+5/5=2
if we choose {5,1,4,2,3,6} then cost is 2+5/6=3
it can be proven that answer is 2.
For query 2, if we choose {1,5} then cost is 0+7/2=4
if we choose {4,1,5,7,8} then cost is 1+7/5=3
if we choose {2,4,1,5,7,8} then cost is 2+7/6=4
if we choose {2,4,1,5,7,8,3,6} then cost is 3+7/8=4
It can be proven that answer is 3


Subtask1(5%): n,m<=20
Subtask2(40%): n,m<=10^5,all seriousness is the same
Subtask3(40%): n<=10^3,m<=10^5
Subtask4(15%): n,m<=10^5 (Unsolable maybe)

Orange boy came and ACed this rubbish problem quickly.

来源:Hell Hole Studios Blog

< <上一篇