用C语言解决下面一个邻接表方面的算法的问题怎么实现的

Problem Description
There is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli.

If you solved the last problem, you will see that the devil can't figure out who is z*p because there are too many people. So anyway, she decided to let it go.

The devil think she is the cutest loli in the world, but there is some people in the kingdom don't think so. And they think WJMZBMR is the most cutest loli.

It seems a war is approaching, but in this kingdom, due to the old tradition, every conflict is solved by Algorithm contest!

One day, WJMZBMR is hanging out with her friend s***kplus on the street. And she noticed that there is a group of people playing algorithm contest to decide who is the cutest loli in the kingdom. One problem attracts her interest:

Given a tree with n vertices, we randomly choose k vertices of it. Then we can induced a subtree which is the smallest connected subtree of the original tree containing those k vertices.

Each vertex has a label(an integer), for a subtree we induced, we look at its diameter a-b,(if there are many diameters, pick the one with the smallest a, and then the smallest b). And output how many distinct label are on the diameter.

What is the expected value we output?

Of course, WJMZBMR is merely a cute loli and don't know much about the algorithm contest, but since you are a member of Princess's Knight, you should solve it for your princess, can you do it?

Input
The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains two integers n,k.
The next n-1 lines, each contains two integers a and b, denote there is an edge between a and b.
The next line contains n integers separated by a single space, denote each vertex's label in the order from 1 to n.

n,k <= 300. label <= 10^9.
T <= 20.

Output
For each case, output the result.
This problem is special judged. The relative error less than 1e-6 will be accepted.

Sample Input
1
20 8
2 1
3 1
4 1
5 4
6 3
7 2
8 4
9 5
10 5
11 10
12 11
13 10
14 11
15 12
16 12
17 14
18 13
19 18
20 17
5 6 2 1 2 4 7 3 1 3 5 4 1 7 2 6 1 2 1 5

1个回答

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

相似问题

0
这个旅行商的问题困扰了很久了,用邻接表怎么实现的?采用C语言
0
一个有关安于邻接矩阵的问题,是如何利用C语言编程实现的呢
0
查找最近的车站的一个算法问题,采用邻接矩阵的方式的表述,怎么计算的,运用C语言的相关知识
0
用邻接表实现距离数组的存储的计算,用C语言的程序编写的方法如何解决
1
用数组表示法(邻接矩阵)和邻接表两种存储结构分别表示下面的无向图。
0
为什么会出现C语言指针指空的呢
2
数据结构图(用C语言)当中为什么邻接表用结构体变量报错,用邻接矩阵不报错?
1
请教数据结构#邻接链表表示图?
0
大佬们,这道题能用c语言写吗?
1
邻接表双向BFS算法数组越界问题
1
编程实现有向图的深度和广度优先遍历
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。
1
求教大佬们,这个“读取位置 0xCCCCCCCC 时发生访问冲突。”的异常该如何解决?
1
C#调用纯C的DLL时,结构体指针、数组、二维数组 怎么转换?
0
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
1
Kruskal算法实现最小生成树主函数的第一行的aaa就无法输出是为什么
1
用c语言版写的求解关键路径,调试到一半按任意键继续就关了,求大神看看我的代码
0
floyd算法求任意两点最短路径,为什么输出的邻接矩阵总不正确
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现
1
c语言实现的套汇问题 钱的种类多了就就不行了