513010 - 迷宫

【题目描述】迷宫(maze)

小光发现自己陷入了一个巨大的迷宫,初始时小光在1号房间。 迷宫由N个房间和连接这些房间的通道组成,每对房间都通过一条且只有一条通道连接。当小光踏入一个房间时,他有可能掉入该房间的陷阱并送回1号房间。也有可能找到该房间的隐藏出口逃离这个迷宫。 小光对整个迷宫的结构一无所知,因此,他每次只是随机选择一条通道。当他在一个房间里时,他有同样的可能性选择连接该房间的任何通道(包括他过去来该房间的通道)。 试计算在他找到出口之前,预计要经过多少通道。

输入

第一行是一个整数T(T≤30),表示测试用例的数量。 每种测试用例第一行都是一个整数N(2≤N≤10000),表示房间数量。 然后给出N-1对整数X,Y(1≤X,Y≤N,X≠Y),表明X和Y之间存在一条通道。 最后,给出了N对整数Ki和Ei(0≤Ki,Ei≤100,Ki+Ei≤100%,K1=E1=0),表示第i个房间掉入陷阱的概率和找到隐藏出口逃离迷宫的概率。

输出

对于每个测试用例,输出一行“case k:”。k是case id,然后是退出之前经过的预期通道数(保留小数点后5位)。如果无法逃离迷宫,则输出“不可能”。

样例

输入

3
3
1 2
1 3
0 0
100 0
0 100
3
1 2
2 3
0 0
100 0
0 100
6
1 2
2 3
1 4
4 5
4 6
0 0
20 30
40 30
50 50
70 10
20 60

输出

Case 1: 2.00000
Case 2: impossible
Case 3: 2.89552
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题