#P9343. 诡术妖姬的闪烁

    ID: 5731 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500省选/NOI-最小费用最大流残量增广路树形 DP动态 DP

诡术妖姬的闪烁

题目描述

诡术妖姬乐芙兰在一棵有 nn 个结点的树上召唤了 mm 个分身。结点 ii 最多能容纳 cic_i 个分身。对每个 2≤i≤n2\le i\le n,结点 ii 与结点 ⌊i/2⌋\lfloor i/2\rfloor 之间有一条长度为 11 的双向边。

第 ii 个分身的初始位置为 pip_i。一共有 mm 轮游戏。第 ii 轮只考虑前 ii 个分身,可以让它们沿树上的边移动,使每个结点最终的分身数都不超过该结点的容量。这轮游戏的代价是这些分身移动距离的总和。

每轮结束后,所有分身都回到初始位置。求每一轮游戏的最小代价。

输入格式

第一行两个整数 n,mn,m。第二行 nn 个非负整数 c1,…,cnc_1,\ldots,c_n。第三行 mm 个整数 p1,…,pmp_1,\ldots,p_m,其中 1≤pi≤n1\le p_i\le n。

输出格式

输出 mm 行,第 ii 行表示第 ii 轮的最小代价。数据保证有解。

样例

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≤n,m≤4×1051\le n,m\le4\times10^5。原题未规定 cic_i 的单独上限。由于每轮至多有 mm 个分身,把任意大于 mm 的容量按 mm 处理不会影响答案。

原赛子任务 nn 上限 mm 上限 原赛分值
1 11 11 1
2 4×1054\times10^5 4
3 2020 10
4 100100 100100 20
5 4×1054\times10^5 15
6 4×1054\times10^5 100100
7 4×1054\times10^5 35

原 PDF 题面