编程介的小学生 2019-01-07 22:58 采纳率: 20.5%
浏览 251
已采纳

用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条回答 默认 最新

  • threenewbee 2019-12-17 23:28
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)