这个小问题,用算法解决的思路是什么,c语言

Problem Description
Mike has just found a dungeon. Inside there are n rooms and p treasure chests. Chests 1,...,p are located in room v1,...,vp 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, Blot’s 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 1k. Please help mike to compute the expected time that Blot collects all p treasures for him.

Input
The first line on the input contains an integer T(T≤10). There will be T test cases. The first line of each test case contains an integer n(2≤n≤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≤100) indicating the number of scenarios. Each of the following q lines represents a scenario which consists of some integers p,v0,v1,...,vp separated by blanks. The first integer p(0<p≤500) indicates there will be p treasure chests. The second integer v0 indicates that Blot is in room v0 at the beginning. For i∈{1,...,p}, the i−th treasure will be spawn at room vi. You may assume vi ≠ vi-1 for every i∈{1,...,p}.

Output
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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
现场求助C语言大身来解决下这个算法难题,关键是怎么计算的思路
1
求差的算法思路,在C语言上的实现,具体看下面的问题,怎么解决?
1
是一个记录去重的算法问题,需要使用C语言的思路去解决的办法?
1
C语言程序设计解决Pipe Fitters的算法问题的正确思路怎么实现
1
采用C语言解决这个距离远近的长短的判断的算法怎么实现?具体的思路谢谢
1
一个姓名的匹配算法的实现过程的分解,数据结构C语言解决这个问题的思路方式
1
计算子数组最大和的一个问题,是不是需要DP的算法,采用C语言解决的思路是什么的?
1
一个由杨辉三角形引申出来的算法的解决思路,采用的是C语言的方式
1
物体碰撞和反弹消除的判断,采用C语言解决这个算法怎么实现思路
0
C语言如何解决这个电梯的算法的问题,运用C语言的代码的思路的实现
0
C语言的编程的技术,去解决这里二进制的序列的一个问题的算法怎么实现的思路
0
求问一次遍历搜索要求下如何才能解决这个问题,使用C语言利用的算法的思路
0
运用C语言是如何解决这里的矩阵的一个转换颠倒的算法的?具体的思路
0
DNA遗传算法的一个难题的解决的思路,怎么运用C语言解决这个题的办法
0
拥有N个定点的无向图的一个算法的问题,采用C语言的程序设计思路的办法来怎么解决的
0
分型树的一个算法的综合的使用问题解决,怎么使用C语言程序的设计思路来实现
0
计算最大质因数的一个算法的问题,怎么利用C语言的程序设计的思路来解决
0
MAP数据结构在搜寻算法的运用,采用C语言的程序的设计的思路解决
0
C语言的绕矩形的正确的移动的问题的算法的解决思路,怎么采用代码编写的方式实现的
1
我是小白,求大神帮忙用raptor解决这道题,不能用C语言,最好有解题思路和算法流程图