TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7292
  • 题目
  • P7292抢购与促销
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    商场开启了“买一送一”的促销购物,消费者们都趁此机会涌入商场疯狂抢购。

    商场里共有 \(n\) 家商铺,商铺之间由 \(n-1\) 条走廊连接,任意两家商铺都可以通过走廊直接或间接的相互到达。商铺编号 \(1,2,\cdots,n\) ,商场的大门在第 \(1\) 家商铺的位置,消费者只能从这里进出商场。

    每个商铺都有一种独特的商品正在出售,第 \(i\) 家商铺的商品售价为 \(p_i\) 。当消费者经过这家商铺时可以购买一件这种商品,也可以不购买。由于促销活动的限制,每个消费者每种商品至多购买 \(1\) 件。所以即使消费者反复多次经过这家商铺,也不能多次购买该商铺的商品。

    促销活动“买一送一”的意思是,消费者每买一件商品下一件商品就免费。也就是说,假如消费者按顺序依次购买了售价为 \(x_1,x_2,x_3,x_4,x_5,\cdots\) 的商品,只需要支付其中第 \(1,3,5,\cdots\) 件商品的费用,即 \(x_1+x_3+x_5+\cdots\) 。显然,即使商品集合相同,购买顺序也可能会影响购买的总费用。

    你也是参与抢购的消费者之一。由于学过信息学竞赛,你在抢购过程中保持了清醒的头脑,打算规划出一条最优的购物路线。最优的购物路线要满足以下条件:

    • 每种商品都要购买恰好一件
    • 从商场大门进入和离开,且在商场中走过的总路程最短
    • 每种商品都在首次路过它所在的商铺时购买
    • 满足以上三个条件的情况下,总费用尽可能小

    商场规模巨大,手工计算最优购物路线非常困难,学过信息学竞赛的你决定写一个程序来计算。

    输入格式

    第一行一个整数 \(n\) ,表示商场中商铺的数量。

    第二行 \(n\) 个整数 \(p_1,p_2,\cdots,p_n\) ,表示每家商铺出售的商品价格。

    接下来 \(n-1\) 行,每行两个整数 \(a_i,b_i\) ,表示商场的一条走廊。

    输出格式

    输出一个整数,按最优购物路线进行购物的总费用。

    样例输入 1

    5
    1 2 4 8 16
    1 4
    1 5
    2 4
    3 4

    样例输出 1

    11

    样例输入 2

    10
    5 3 9 7 8 9 3 1 8 2
    1 2
    1 3
    1 4
    4 5
    1 6
    6 7
    1 8
    8 9
    9 10

    样例输出 2

    18

    提示

    样例1解释

    符合前三个条件的购物路线有四条:

    • 依次经过商铺 \(1,4,2,4,3,4,1,5,1\) ,按售价为 \(1,8,2,4,16\) 的顺序购买商品,总费用为 \(1+2+16=19\)
    • 依次经过商铺 \(1,4,3,4,2,4,1,5,1\) ,按售价为 \(1,8,4,2,16\) 的顺序购买商品,总费用为 \(1+4+16=21\)
    • 依次经过商铺 \(1,5,1,4,2,4,3,4,1\) ,按售价为 \(1,16,8,2,4\) 的顺序购买商品,总费用为 \(1+8+4=13\)
    • 依次经过商铺 \(1,5,1,4,3,4,2,4,1\) ,按售价为 \(1,16,8,4,2\) 的顺序购买商品,总费用为 \(1+8+2=11\)

    因此最优路线的总费用为 \(11\)

    样例2解释

    最优的购物路线不唯一,其中一种是依次经过商铺 \(1,6,7,6,1,3,1,4,5,4,1,8,9,10,9,8,1,2,1\) ,按售价为 \(5,9,3,9,7,8,1,8,2,3\) 的顺序购买商品。

    数据范围

    本题按子任务捆绑测试,每个子任务有多组测试数据,通过该子任务所有数据才能获得该子任务的分数。

    子任务 \(1(2\%)\)\(n\leq 5\times 10^5\) ,所有 \(p_i =1\)
    子任务 \(2(4\%)\)\(n\leq 11\)
    子任务 \(3(5\%)\)\(n\leq 100\) ,每家商铺至多连接 \(10\) 条走廊
    子任务 \(4(11\%)\)\(n\leq 100\)\(0\leq p_i\leq 1\)
    子任务 \(5(10\%)\)\(n\leq 100\)
    子任务 \(6(22\%)\)\(n\leq 3000\)
    子任务 \(7(10\%)\)\(n\leq 5\times 10^5\)\(0\leq p_i\leq 1\)
    子任务 \(8(11\%)\)\(n\leq 5\times 10^5\) ,除了商铺 \(1\) 以外,每个商铺至多连接 \(2\) 条走廊
    子任务 \(9(12\%)\)\(n\leq 5\times 10^5\) ,所有商铺连接的走廊数量为奇数
    子任务 \(10(13\%)\)\(n\leq 5\times 10^5\)

    所有测试数据: \(1\leq n\leq 5\times 10^5\)\(0\leq p_i\leq 10^9\)\(1\leq a_i,b_i\leq n\)

    OJ上只放了子任务10的数据