#3068. 「2019 集训队互测 Day 1」学习轨迹

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: cz_xuyixuan

题目描述

马上就要比赛了,小 D 决定突击学习一些算法。

他要学习的算法共有 n 个,这些算法被依次标号为 1,2,\cdots,n

小 D 根据学习难度以及实用价值等方面,给每个算法定了一个价值。其中,编号为 i 的算法的价值是 w_i

小 D 想要以某种顺序学完所有的这 n 个算法。我们把他学习的顺序可以看做一个 1,2,\cdots,n 的排列 p ,其中第 i p_i 表示第 i 个学习的算法的编号。

小 D 不希望连续学习的算法之间价值差异过大。对于一种学习方案,他定义这种方案的代价为相邻两个学习的算法的价值差之和。形式化地,对于排列 p ,我们定义他的权值 w(p) 为:

w(p)=\sum_{i=1}^{n-1}\left \lvert w_{p_i}-w_{p_{i+1}} \right \rvert

但是,小 D 很快发现了一些问题:有的算法之间具有依赖关系,例如学习 LCT 需要先学习 Splay。小 D 把这些算法分成了两类:基础算法和延伸算法

基础算法共有 m 个,为了方便,小 D 把它们编号为 1,2,\cdots,m ;延伸算法是剩下的 n-m 个算法,编号为 m+1,m+2,\cdots,n

对于每个延伸算法 i(m+1\le i\le n) ,该算法会依赖恰好一个基础算法,记作 u_i(1\le u_i\le m) 。即,算法 i 必须要在算法 u_i 之后学习

小 D 想要知道,在所有满足这些依赖关系的学习序列 p 中, w(p) 最小的那一个

因为小 D 还没开始学这 n 个算法,所以他并不会算。请你帮他求出 w(p) 的最小值,以及一个取到该最小值的排列 p

输入格式

从标准输入读入数据。

第一行包括两个空格隔开的整数 n,m ,分别表示算法的总数,基础算法的个数。

第二行包括 n 个空格隔开的整数,其中第 i 个数 w_i 表示算法 i 的价值。

第三行包括 n-m 个空格隔开的整数,其中第 i 个数 u_{m+i} 表示延伸算法 m+i 依赖的算法的编号。

输出格式

输出到标准输出。

第一行包括一个整数,表示 w(p) 的最小值。

第二行包括 n 个空格隔开的整数,其中第 i 个数 p_i 表示最优解中,第 i 个学习的算法编号。

可以证明,在题目的限制下,小 D 一定可以学完所有的算法,即合法的 p 一定存在。如果有多个使 w(p) 取最小值的合法的 p ,你可以输出其中任意一个。

样例

样例输入

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

样例输出

7
2 3 1 4 5 6

数据范围与提示

评分方式

对于每组测试数据,若你输出的 w(p) 是正确的,则你可以得到该测试点 60\% 的分数。

此外,若你输出的排列 p 是一组可以使 w(p) 取最小值的合法方案,则你可以得到该测试点剩余 40\% 的分数。

请注意,即使对于某些测试点,你可能只想要得到部分分,但是你仍然需要严格按照输出格式进行输出。

子任务

对于所有测试数据, 1\le n\le 10^{6} 1\le m\le n 1\le w_i\le 10^{12} 1\le u_i\le m(m+1\le i\le n)

本题共 7 个子任务,对于每个子任务,你的得分为你在该子任务中所有测试数据上得分的最低者。

各子任务的特殊限制见下表:

子任务编号 分值 n 特殊限制
1 5 \le 10^5 m=n
2 5 \le 10
3 10 \le 20
4 10 \le 10^5 \forall 1\le i\le n,w_i\le 10
5 30 \le 5000
6 20 \le 10^5
7 20 \le 10^6