All submissions for this problem are available.
There are n different locations (0 to n-1) connected by n-1 bidirectional roads forming a connected tree.There are m different troops present at these locations such that more than one troop can be present at single location and some locations can be empty without any troop.Because of the orders of the Mad king, all the troops have to change their locations which is given by the following function.
For a troop situated at location i :
int new_location ( int i, int n)
while(temp == i)
If there are more than 1 troop situated at location i, the function is called separately for every troop.
The troops change their positions simultaneously.A road is called lucky road if it is traversed by all the troops during the switching of the locations. Find the expected number of such Lucky roads .
- First line contains T, number of test cases. Followed by T test cases each containing 3 lines.
- The first line gives n,m the number of locations and the number of troops.
- The next n-1 lines contain n-1 roads (a,b) ie. road joining locations a and b.
- The third line contains m indexes giving the locations of troops. Indexing of locations is 0 based (0 to n-1).
- T lines each containing the expected number of lucky roads in that system.
Give your answer with exactly 6 decimal places.
- 1 ≤ T ≤ 100
- 2 ≤ n ≤ 100
- 1 ≤ m ≤ 10
Input: 1 3 1 0 1 1 2 0 Output: 1.500000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.