Loading web-font TeX/Math/Italic
比赛场次 648
比赛名称 20241128
比赛状态 已结束比赛成绩
开始时间 2024-11-28 07:30:00
结束时间 2024-11-28 12:00:00
开放分组 全部用户
注释介绍
题目名称 外卖
输入输出 food.in/out
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar小金 AAAAAAAAAA 0.359 s 4.28 MiB 100
Gravatarflyfree AAAAAAAAAA 0.411 s 4.87 MiB 100
Gravatar┭┮﹏┭┮ AAAAAAAAAA 0.428 s 5.04 MiB 100
GravatardarkMoon AAAAAAAAAA 0.513 s 4.87 MiB 100
Gravatar黄天乐 WTTTTTTEEE 18.673 s 3.17 MiB 0

外卖

★★☆   输入文件:food.in   输出文件:food.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

Kreso最近找了份送外卖的兼职工作。

在A市有n家餐馆,编号为1\sim n。它们由恰好n-1条路相连,使得任意两家餐馆相互可达。每天,Kreso首先要花费m单位时间从这些餐馆取外卖。

Kreso最初位于1号餐馆。每1单位时间,他要么从所在餐馆取出外卖;要么移动到一个相邻的餐馆。注意,经过一个餐馆并不会取外卖,取外卖要单独花费1单位时间。

n家餐馆的外卖价值分别是a_1a_n。请问在这次取外卖的过程中,Kreso取得的所有外卖的价值之和最大是多少?

【输入格式】

第一行,两个正整数n,m

第二行,n个用空格隔开的正整数a_1,\cdots,a_n

接下来n-1行,每行两个整数u,v,表示有一条路连接u号餐馆和v号餐馆。

【输出格式】

输出一行,一个整数,表示答案。

【样例输入】

3 5
9 2 5
1 2
1 3

【样例输出】

14

【样例说明】

Kreso首先花费1单位时间取出1号餐馆外卖,然后花费1单位时间移动到3号餐馆,然后花费1单位时间取出3号餐馆外卖,剩余2单位时间无用。取得外卖价值之和为9 + 5 = 14

【样例下载】

样例下载

【数据规模与约定】

对于30\%的数据,1\leq n,m\leq 100

对于100\%的数据,1\leq n,m\leq 500,1\leq u,v\leq n,1\leq a_i\leq 10^6