比赛场次 | 648 |
---|---|
比赛名称 | 20241128 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2024-11-28 07:30:00 |
结束时间 | 2024-11-28 12:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 外卖 |
---|---|
输入输出 | food.in/out |
时间限制 | 2000 ms (2 s) |
内存限制 | 512 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
|
AAAAAAAAAA | 0.359 s | 4.28 MiB | 100 |
|
AAAAAAAAAA | 0.411 s | 4.87 MiB | 100 |
|
AAAAAAAAAA | 0.428 s | 5.04 MiB | 100 |
|
AAAAAAAAAA | 0.513 s | 4.87 MiB | 100 |
|
WTTTTTTEEE | 18.673 s | 3.17 MiB | 0 |
Kreso最近找了份送外卖的兼职工作。
在A市有n家餐馆,编号为1\sim n。它们由恰好n-1条路相连,使得任意两家餐馆相互可达。每天,Kreso首先要花费m单位时间从这些餐馆取外卖。
Kreso最初位于1号餐馆。每1单位时间,他要么从所在餐馆取出外卖;要么移动到一个相邻的餐馆。注意,经过一个餐馆并不会取外卖,取外卖要单独花费1单位时间。
设n家餐馆的外卖价值分别是a_1到a_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。