Asya & Coloring
All submissions for this problem are available.
Asya is a very intelligent girl and she comes up with very fascinating games to entertain herself.
On her b'day she got gifts from Uncle Sai. He gifted her M marbles and a tree with N nodes with each edge of 1-unit length. Asya could keep M marbles in the nodes of the tree and then see them roll from one node to some other node where the marble stops. A marble always ends at some other node than what it started from.
After playing a while Asya got bored and thought of making it a lil more interesting. She took her color box and painted every marble differently (with distinct colors). After this she placed these marbles in the tree nodes. Some tree nodes might be empty and some tree nodes may have more than one marble. The marbles then started rolling, painting the edges of the tree.
Asya calls an edge beautiful if that edge is colored by all the M colors.
Given the tree and initial arrangement of the marbles in the tree and the fact that a marble can end at any other node with equal probability, can you tell Asya the expected value of total length of beautiful edges.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of nodes in the tree.
- N-1 lines follow, each containing two space separated integers, X and Y denoting an edge between node X and Y.
- The last line of every test case contains N space separated integers, denoting number of marbles at i-th node.
- For each test case, output a single line containing the expected value of total length of beautiful edges.
- The answer with absolute or relative error no more than 10-6 will be accepted.
- 1 ≤ T ≤ 10
- 3 ≤ N ≤ 105
- 1 ≤ M ≤ 102
- 0 ≤ Node number < N
Input: 1 3 0 1 1 2 1 0 1 Output: 1.0000
Example case 1.
There are four possible cases :
- Case 1 : Marble at node 0 stops at node 1 and marble at node 2 stops at node 1. In this case there is no beautiful edge.
- Case 2 : Marble at node 0 stops at node 2 and marble at node 2 stops at node 1. In this case the total length of beautiful edges is 1, (edge between node 1 and node 0).
- Case 3 : Marble at node 0 stops at node 1 and marble at node 2 stops at node 0. In this case the total length of beautiful edges is 1, (edge between node 0 and node 1).
- Case 3 : Marble at node 0 stops at node 2 and marble at node 2 stops at node 0. In this case the total length of beautiful edges is 2, (both the edges).
- So, the final answer is (1/4)*0 + (1/4)*1 + (1/4)*1 + (1/4)*2 = 1
Note : Use of fast I/O is recommended
|Tags||expected-value, ipc15p3b, medium-hard, pakhandi, probability, tree|
|Time Limit:||2 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.