主页 讨论版 问题 名次 状态 统计
欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~
问题 I: Ar老师的环球旅行

问题 I: Ar老师的环球旅行

时间限制: 1 Sec  内存限制: 128 MB
提交: 18  解决: 4
[提交][状态][讨论版]

题目描述

哇,一年一度的七夕节到啦,Ar老师和女朋友准备了一趟环球旅行,于是Ar老师打开了世界地图,选取了N个地方作为理想的旅游目的地,但是由于经费有限,他只能去K个地方玩耍,并且K个地点最好是连续的一条路线。同时为了取悦小女友,Ar老师给每个地方的美观度评了分(Vi<=1000000),Ar老师希望所去的景区的美观度之和最大。为了简化问题,Ar老师选取的N个地点构成了一个恰好都联通的树形图,而显然,Ar老师去的路线即为图上一条路径。请你帮忙找一个最好的方案,使得Ar老师所去的美观度之和最大,并且输出首尾结点。若没有这样的方案,输出“no solution”。

输入

输入第一行包含两个整数,N和K(N<=10000,K <= N)

第二行包含N个整数,表示第i个地点的美观度(Vi<=1000000)

接下来N-1行,每行两个整数u,v表示结点u,v之间有一条连线(1<=u,v<=N)

输出

输出美观度之和最大值,以及该路径的首尾结点(首尾结点要求先输出编号小的)

如果存在两条路径取到最大值,输出首尾结点字典序小的一条(如1 2;1 3,则输出1 2)

若不存在方案,输出no solution

样例输入

5 4
2 5 2 3 3
1 2
1 3
2 4
2 5

样例输出

12 3 4

提示

PS:如果图上没有一条链长度为K,则不存在方案。

[提交][状态][讨论版]