#1026. 队列染色

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mars_Dingdang

题目描述

有一棵 n 个结点的树,每个节点都有一个权值 a_i 。现在要将这棵树的结点全部染色,规定如下:

  1. 根节点 r 可以随时被染色
  2. 对于其他节点,其在被染色之前其父亲节点必须已经染色。

k 次染色的代价为 k\times a_i k 类似时间戳。求将整棵树染色的最小总代价。

然后,假设你第 k 次染色的结点为 u_k ,则你将得到一个“有色序列” b_i ,且 b_k=a_{u_k}

你需要对这 n 个整数 b_i 进行排序,但你手头能用的工具只有若干个双端队列。

你必须依次处理这 n 个数,对于每个数 b_i ,你可以进行以下两个操作之一:

  1. 新建一个双端队列,并将 b_i 作为这个队列中唯一的数。

  2. b_i 从已有双端队列的队头或队尾入队。

除此之外,对所有的数处理完成后,你需要将这些双端队列按照一定的顺序连起来,得到一个非降序的长度为 n 的序列,请问你最少需要几个双端队列?

输入格式

第一行为两个正整数 n,r ,表示树的结点数(即有色序列的长度)以及根节点编号。

接下来一行 n 个正整数 a_i

接下来 n-1 行,每行两个正整数 a, b ,表示 a b 的父亲节点。保证数据合法。

输出格式

输出共两行,第一行表示最小代价,第二行表示最少的双端队列数量。

样例

Input:

10 9
99 90 21 12 23 80 4 37 48 40 
3 4
10 6
10 7
3 8
9 10
9 3
9 5
2 1
9 2

Output:

1802
3

数据范围与提示

样例解释

选择的结点顺序为 9, 2, 1, 10, 6, 3, 8, 5, 4, 7 ,计算得最小代价为 1802

b 序列为 \{48, 90, 99, 40, 80, 21, 37, 23, 12, 4\}

对于 48 ,新建一个双端队列,元素为 (48)

对于 90 ,新建一个双端队列,元素为 (48),(90)

对于 99 ,从队尾插入第二个,元素为 (48),(90,99)

对于 40 ,从队首插入第一个,元素为 (40,48),(90,99)

对于 80 ,从队尾插入第一个,元素为 (40,48,80),(90,99)

对于 21 ,新建一个双端队列,元素为 (21),(40,48,80),(90,99)

对于 37 ,从队首插入第二个,元素为 (21),(37,40,48,80),(90,99)

对于 23,12,4 ,从队尾、队首、队首插入第一个,元素为 (4,12,21,23),(37,40,48,80),(90,99)

顺次链接即可。因此最少需要三个。


数据范围

Subtask1: 对于 50\% 的数据, 1\le n\le 1000 1\le a_i\le 1000

Subtask2: 对于 100\% 的数据, 1\le n\le 10^5 1\le a_i\le 10^5