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

Robot Dog

Time Limit: 3000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 582    Accepted Submission(s): 185

Problem Description
Mike has just found a dungeon. Inside there are n rooms and p treasure chests. Chests $1, . . . , p$ are located in room $v_1, . . . , v_p$ respectively. The rooms are connected by $n - 1$ passages. Any two rooms connected by a passage are considered adjacent. This dungeon is very special that there exists a path between any two rooms. Among these treasure chests, only chest 1 can be taken in the very beginning, others must be taken in order. That is, only after chest i is taken, may chest $i + 1$ be taken as well, for every $i \{1, . . . , p - 1\}$.

Mike is lazy, so he dislikes to explore the dungeon on his own feet. Therefore, Mike sends his robot dog, Blot, to collect the treasures in the dungeon. Blot can automatically collect the treasures from the chests, and it takes Blot exactly a second to move to any adjacent room. However, Blots movement is uncontrollable. Blot moves to all adjacent rooms with the same probability. For example, if there are $k$ adjacent rooms, then Blot will move to any of them with probability $\frac{1}{k}$. Please help mike to compute the expected time that Blot collects all $p$ treasures for him.

The first line on the input contains an integer $T (T \leq 10)$. There will be $T$ test cases. The first line of each test case contains an integer $n (2 \leq n \leq 50000)$ indicating the number of rooms in the dungeon. The rooms are numbered from $0$ to $n - 1$. Each of the following $n - 1$ lines contains two integers $u$ and $v (u, v \{0, . . . , n - 1\})$ indicating room $u$ and room $v$ are adjacent.

The next line contains an integer $q (q \leq 100)$ indicating the number of scenarios. Each of the following $q$ lines represents a scenario which consists of some integers $p, v_0, v_1, . . . , v_p$ separated by blanks. The first integer $p (0 < p \leq 500)$ indicates there will be $p$ treasure chests. The second integer $v_0$ indicates that Blot is in room $v_0$ at the beginning. For $i \{1, . . . , p\}$, the $i-th$ treasure will be spawn at room $v_i$. You may assume vi $\neq$ vi-1 for every $i \{1, . . . , p\}$.

For each test case, output $q$ lines, and the $j-th$ of them corresponds to the $j-th$ scenario of the test case. For each scenario, output the expected time in seconds such that Blot collects all treasures. Print the answer to the fourth decimal place, and separate two consecutive test cases with a blank line.

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

Sample Output
1.0000 5.0000 11.0000


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-04-15 23:43:53, Gzip enabled