比赛场次 492
比赛名称 EYOI常规赛 1st
比赛状态 已结束比赛成绩
开始时间 2021-12-15 18:40:00
结束时间 2021-12-15 21:10:00
开放分组 全部用户
注释介绍
题目名称 树染色
输入输出 colortree.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

树染色

★★☆   输入文件:colortree.in   输出文件:colortree.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

一颗树有 $n$ 个节点,这些节点被标号为:$1,2,3…n$,每个节点 $i$ 都有一个权值 $A[i]$。

现在要把这棵树的节点全部染色,染色的规则是:

    根节点$R$可以随时被染色;对于其他节点,在被染色之前它的父亲节点必须已经染上了色。

    每次染色的代价为$T*A[i]$,其中$T$代表当前是第几次染色。

求把这棵树染色的最小总代价。

【输入格式】

第一行包含两个整数 $n$ 和 $R$ ,分别代表树的节点数以及根节点的序号。

第二行包含 $n$ 个整数,代表所有节点的权值,第 $i$ 个数即为第 $i$ 个节点的权值 $A[i]$。

接下来 $n-1$ 行,每行包含两个整数 $a$ 和 $b$ ,代表两个节点的序号,两节点满足关系: $a$ 节点是 $b$ 节点的父节点。

除根节点外的其他 $n-1$ 个节点的父节点和它们本身会在这 $n-1$ 行中表示出来。

同一行内的数用空格隔开。

【输出格式】

输出一个整数,代表把这棵树染色的最小总代价。

【样例输入】

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

【样例输出】

33

【数据范围】

$1≤n≤1000,1≤A[i]≤1000$

【来源】

《算法竞赛进阶指南》