GS  Going to school
Your family has just moved to small town with simple transportation system: there are N junctions and N  1 roads connecting the junctions. These roads guarantee that it’s possible to travel between any two junctions. Each road connects two junctions and has a preferred value.
You are new here and not familiar with the roads. So when you stay at a junction which is not your destination, you will choose one of incident roads to walk (even it makes you get farther from your destination). The probability of choosing one road equals to its preferred value divide to total preferred value of all incident roads. For example, if there are three incident roads at current junction with preferred value 1, 2 and 3, the probability of choosing each road is 1/6, 2/6 and 3/6, respectively.
Given the starting junction where your house is and the final junction where is your school, what is the expected number of roads you have to walk to reach the destination?
Input
The input begins with T – number of test cases. For each test case, there will be:
 The first line consists of N, st, en  number of junctions, starting and final junction.
 In next N  1 lines, each line consists of three positive integers u, v and c indicate that there is a road between junction u and v with preferred value c.
Output
For each test case, print the expected number of roads you have to walk, round to exactly 5 precision digits.
Limits
T <= 20
1 <= N <= 15
All numbers in input <= 100
Sample
Input 1 3 2 3 1 2 1 2 3 1 Output 3.00000
Explanation
There are 50% chance of going 23 directly; 25% chance of going 2123, 12.5% of going 212123 and so on. The result equals 1 × 50% + 3 × 25% + 5 × 12.5% + … = 3
hide comments
parth2002:
20210513 12:37:07
If you are stuck and cannot think of anything, refer to this blog 

Added by:  sieunhan 
Date:  20091129 
Time limit:  0.100s3.134s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Khuc Anh Tuan  ACM Vietnam Practice 