#P9343. 诡术妖姬的闪烁
诡术妖姬的闪烁
题目描述
诡术妖姬乐芙兰在一棵有 个结点的树上召唤了 个分身。结点 最多能容纳 个分身。对每个 ,结点 与结点 之间有一条长度为 的双向边。
第 个分身的初始位置为 。一共有 轮游戏。第 轮只考虑前 个分身,可以让它们沿树上的边移动,使每个结点最终的分身数都不超过该结点的容量。这轮游戏的代价是这些分身移动距离的总和。
每轮结束后,所有分身都回到初始位置。求每一轮游戏的最小代价。
输入格式
第一行两个整数 。第二行 个非负整数 。第三行 个整数 ,其中 。
输出格式
输出 行,第 行表示第 轮的最小代价。数据保证有解。
样例
20 20
0 1 0 2 0 0 4 1 2 1 1 0 2 0 0 3 2 0 0 2
16 10 3 3 19 10 8 14 17 12 3 10 14 2 20 5 18 19 5 16
0
0
1
2
3
4
4
5
5
7
8
9
11
11
12
14
15
17
21
21
数据范围
。原题未规定 的单独上限。由于每轮至多有 个分身,把任意大于 的容量按 处理不会影响答案。
| 原赛子任务 | 上限 | 上限 | 原赛分值 |
|---|---|---|---|
| 1 | 1 | ||
| 2 | 4 | ||
| 3 | 10 | ||
| 4 | 20 | ||
| 5 | 15 | ||
| 6 | |||
| 7 | 35 | ||