这个图的问题,使用邻接表的方法,怎么使用数据结构解决?

Problem Description
Lady CA has a tree with n points numbered 1,2,...,n, and each edge has its weight. The unique route connecting two points is called a chain, and the length of a chain equals the sum value of the weights of the edges passed.
The point number m is called the root. Lady CA defines a special kind of chain called folded chain, the chain connecting the points numbered x,y(x≠y) is called a folded chain, if and only if the chain connecting the point numbered x and the root doesn't pass the point numbered y, and the chain connecting the point numbered y and the root doesn't pass the point numbered x.
Lady CA wants to find the length of the kth longest folded chain. Notice that the chain connecting the points numbered x,y and the chain connecting the points numbered y,x are the same.

Input
The first line contains an integer T(1≤T≤3)——The number of the test cases. For each test case:
The first line contains three integers n(2≤n≤50,000),m(1≤m≤n),k(1≤k≤n×(n−1)2). Between each two adjacent integers there is a white space separated.
The second line to the nth line describes the n−1 edges in the graph. Each line contains three integers u,v(1≤u,v≤n,u≠v),w(1≤w≤10,000), which means there is an edge which has a weight w connecting the points numbered u,v. Between each two adjacent integers there is a white space separated.

Output
For each test case, the only line contains the only integer that is the length of the kth longest folded chain. If the kth longest folded chain doesn't exist, print NO.

Sample Input
2
5 1 3
1 2 8
1 5 4
2 3 5
2 4 6
5 1 5
1 2 8
1 5 4
2 3 5
2 4 6

Sample Output
12
NO

1个回答

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

相似问题

0
各位大神能看一下我这个邻接表的深度优先遍历错在哪了吗,为什么运行不出来?
1
自己初始化邻接表数据有问题 (注视是瞎写的)如果还有其他问题也请帮忙改一下
0
求帮助!C语言 图 邻接表文件怎么读取
1
数据结构采用邻接表算法实现KAMI问题,怎么实现的,采用的C语言
1
用C语言解决下面一个邻接表方面的算法的问题怎么实现的
3
C++ vector存邻接矩阵结构体
0
这个旅行商的问题困扰了很久了,用邻接表怎么实现的?采用C语言
0
一个有关安于邻接矩阵的问题,是如何利用C语言编程实现的呢
0
查找最近的车站的一个算法问题,采用邻接矩阵的方式的表述,怎么计算的,运用C语言的相关知识
0
用邻接表实现距离数组的存储的计算,用C语言的程序编写的方法如何解决
1
用数组表示法(邻接矩阵)和邻接表两种存储结构分别表示下面的无向图。
2
数据结构图(用C语言)当中为什么邻接表用结构体变量报错,用邻接矩阵不报错?
1
请教数据结构#邻接链表表示图?
1
邻接表双向BFS算法数组越界问题
0
用邻接矩阵创建有向网,求最小生成树,最短路径(c语言)。
1
求教大佬们,这个“读取位置 0xCCCCCCCC 时发生访问冲突。”的异常该如何解决?
0
CCPC2019-秦皇岛F HDU-6736为什么这个题目把前向星换成邻接表就能AC啊?
0
在Windows7 64位+VS2015上运行求解AOE网关键路径的算法,邻接表表示的AOE网提示网中有回路,邻接矩阵表示的AOE网显示正确的信息?使用的算法是一样的,两种方法的相关类的接口函数也一致,为什么会出现这种问题?
0
利用普利姆算法和克鲁斯卡尔算法实现最小生成树问题C语言或者C++语言实现