#1962. 学习轨迹

    ID: 1962 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest311来源:qoj.ac数据:公开样例排序

学习轨迹

学习轨迹

题目描述

标题: 学习轨迹 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

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

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

w(p)=∑i=1n−1|wpi−wpi+1|

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

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

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

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

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

输入格式

从标准输入读入数据。

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

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

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

输出格式

输出到标准输出。

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

第二行包括 n 个空格隔开的整数,其中第 i 个数 pi 表示最优解中,第 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≤n≤106,1≤m≤n,1≤wi≤1012,1≤ui≤m(m+1≤i≤n)。

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

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

子任务编号 分值 n 特殊限制 1 5 ≤105 m=n 2 5 ≤10 无 3 10 ≤20 4 10 ≤105 ∀1≤i≤n,wi≤10 5 30 ≤5000 无 6 20 ≤105 7 20 ≤106

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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