Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hirak Rajar Desh

By curly_braces · Limits 2s, 1.0 GB

Hirak Raja, the king of the country “Hirak Rajar Desh”, the conqueror ultimate, wanted to expand his kingdom. So, he decided to attack the Goopy kingdom. The Goopy kingdom consists of nn islands (numbered from 1 to nn) and n1n-1 bridges. Each island has a leader with a leadership value 1Li1001 \leq L_i \leq 100. Each bridge connects two different islands and it is possible to travel from any island to any other island within the Goopy kingdom using the bridges.

Hirak Raja wanted to conquer some islands from the Goopy kingdom. To conquer an island, Hirak Raja has to capture the leader of that island. Hirak Raja started his mission from island uu. After conquering an island, he uses a bridge to move to another island that has not been conquered yet. He continues his mission for a while. After reaching island vv, he stops and comes back to Hirak Rajar Desh with the captured leaders. Hirak Raja’s prison has kk cells in which he has to put those captured leaders. Each cell can contain an infinite amount of prisoners. He will put the leaders into cells in such a way that they cannot plan any conspiracy against him.

In cell ii, if the maximum leadership value amongst leaders is XiX_iand the minimum is YiY_i, then the probability that a conspiracy is forming within that cell is Pi=(XiYi)/100P_i=(X_i-Y_i)/100. The probability that Hirak Rajar Desh is in danger is: maxi=1,2,k(Pi)\max\limits_{i=1, \, 2, \, \dots \, k}(P_i). That means the maximum of all Pi(i=1,2,,k)P_i \, (i=1,2,…,k). As Hirak Raja wants to save his throne, he will put the leaders in cells in such a way that the probability of his kingdom being in danger is minimized.

You have to answer qq different queries. Each query consists of 3 integers uu, vv, and kk. You have to find out the probability that Hirak Rajar Desh is in danger if he started his attack from island uu and ended in island vv and there are kk cells in the prison.


Input starts with two integers n,qn,q (1n106,1q2×1051 ≤ n\leq 10^6, 1\leq q \leq 2\times 10^5) denoting the number of islands and number of queries to be answered.

The next n1n-1 lines contain 22 integers x,y(1x,yn)x, y \, (1≤ x, \, y≤ n) each, denoting there is a bridge between island xx and island yy.

The next line contains nn integers, the leadership values L1,L2,,LnL_1, L_2,\dots,L_n(1Li100)1 \leq L_i \leq 100).

The next qq lines contain one query each. Each query consists of 3 integers uu, vv and kk(1u,vn;1k1001\leq u,v \leq n ; 1\leq k \leq 100 ) as described above.

Reminder: Dataset is huge. Please consider using faster I/O methods.


For each query, print the probability that Hirak Raja’s kingdom is in danger. You have to print the probability in percentage. For example, if the probability is 0.37, you have to print 37%.


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



0% Solution Ratio


Login to submit


Let’s assume we know all the leadership values of the captured ones, now how would you place them in...

Toph uses cookies. By continuing you agree to our Cookie Policy.