F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Map

Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 691    Accepted Submission(s): 234


Problem Description
There are N pieces of fragments, and we¡¯re going to select some of them to form a map. Some fragments can be selected into the map directly (named 1-level fragments), while each of the rest follows exactly one fragment as its prior fragment. If B follows A and A is an i-level fragment, then B is defined as an (i + 1) - level fragment, and B can be selected only if A has been selected before. Besides, a fragment is followed by at most one other fragment.

Each fragment is assigned with a reliability. The reliability of the whole map is sum up by two parts:
1.The sum of reliabilities of all selected fragments;
2.If there are xi i-level fragments in total and we select yi(yi > 1) fragments among them to form the map, the reliability would increase by ,where Si denotes the sum of reliabilities of selected fragments in level i.

Please figure out the expectation of reliability of the map under the condition that all valid selections are equiprobable.

At least one fragment should be selected.
 

Input
There are several test cases. The number of test cases T (T<=10) occurs in the first line of input.

For each test case:
The first line consists of two integers N, M (1<=N<=10000,0<=M<N), indicating the number of fragments and relationships respectively.
The second line contains N integers, which describes the reliability of each fragment. The given reliability ranges from 1 to 100, inclusive.
Each of the following M lines contains two integers A and B, which denotes
B follows A(0<=A,B<=N-1).

You may assume that the number of 1-level fragments are no more than 10, and levels will not exceed 1000. No fragment will follow itself directly or indirectly.
 

Output
For each test case, output the expectation with 3 decimal places.
 

Sample Input
2 2 0 1 2 3 1 1 2 4 1 2
 

Sample Output
3.000 5.000
 

Hint
In the first sample, there¡¯re three ways of selections: {0,1}, {0},{1},which respectively generates 6, 1 and 2 of reliability. Hence, the expectation is 3.
 

Author
BUPT
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-06-17 02:30:44, Gzip enabled