問題文
高桥从他姐姐那里收到了一个木制玩具作为生日礼物。
木制玩具 N 球和 N-1 由一本书的各个部分组成。每个球都有 每个部分的编号最大为 1 从 N 。 编号至 1 从 N-1 。
N-1 本书的章节有所不同。 2 连接两个球体,所有球体的方向都是从编号较高的球体到编号较低的球体。还有,球 除 1 之外的每个球都有一个从该球指向另一个编号较小的球的节点。
每个球都准确无误 可以存储 1 整数。第一、球体 i (1 ≦ i≦ N) 是一个整数 s_i 已存储。
高桥和他的妹妹在场。 我决定使用 M 整数玩一个木制玩具游戏。
游戏的目标是使木制玩具每个球体中存储的整数之和尽可能大。
高桥君 M 次。
- 您手头的整数 1 拿出一个。i (1 ≦ i ≦ M) 第二步提取的整数为 t_i 。
- 执行以下操作之一:
- 对木制玩具不做任何事情,整数 丢弃 t_i 。
- 来自组成木制玩具的球 1 选择一个整数 输入 t_i 。 当放置整数时,
球 j (1 ≦ j ≦ N) 执行以下操作。 当
- j = 1 时,球体 1 丢弃原来存储的整数并 存储放置在 1 中的整数。
- j ≧ 2 时,球体 j 将原来存储的整数转换为球体 将来自 j 的节点放置在目标球体上,并且 j 中的整数。
高桥和他的妹妹在木制玩具停止变化之前无法继续下一步。
最后,找到木制玩具每个球体中存储的整数的最大可能总和。
入力
输入将以以下格式从标准输入给出。
N
s_1
s_2
:
s_N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
M
t_1
t_2
:
t_M
- 1 行包含一个整数,表示组成我姐姐给我的木制玩具的球的数量。 N (2 ≦ N ≦ 5,000) 给出。
- 2 从行 N 行提供有关最初存储在球体中的整数的信息。这些 N 从行顶部开始 i (1 ≦ i ≦ N) 行是一个整数 给出了 s_i (1 ≦ s_i ≦ 1,000,000,000) 。这是一个球 i 以整数开头 s_i 已存储。
- N+2 从行 N-1 行提供有关该子句的信息。这些 N-1 从行顶部开始 i (1 ≦ i ≦ N-1) 行是一个整数 给出了 a_i, b_i (1 ≦ a_i < b_i ≦ N) 用空格分隔。这是一个球 b_i 走出球体 表示有一个子句属于 a_i 。
- 2N+1 行包含一个整数,表示手头的整数数量。 M (1 ≦ M ≦ 5,000) 给出。
- 2N+2 从行 M 行提供有关当前整数的信息。这些 给出了 M 从行顶部开始 i (1 ≦ i ≦ M) 行是一个整数 给出了 t_i (1 ≦ t_i ≦ 1,000,000,000) 。这是i 步骤中的整数 代表提取 t_i 。 满足
部分点
针对此问题设置了部分分数。
- N ≦ 7 和 M ≦ 8 的数据集 如果您正确回答 1 , 给出10 点。 如果您对
- N ≦ 16 的数据集 如果您正确回答 2 的回答正确,除上述之外, 20 点。 如果您对
- 没有附加约束的数据集 3 的回答正确,除上述之外, 70 点。 如果您对
出力
最后,木制玩具每个球体中存储的整数的最大可能总值为 在 1 行输出。还在输出末尾添加换行符。
入力例1
7 4 7 5 1 5 2 4 1 2 1 3 1 4 2 5 2 6 6 7 8 2 8 1 3 6 3 7 5
出力例1
40
请按照以下步骤操作。 摘录
- 整数 2 。不要对木制玩具做任何事情。 摘录
- 整数 8 。木制玩具球 将其放入 4 。
- 整数 1 。不要对木制玩具做任何事情。 摘录
- 整数 3 。不要对木制玩具做任何事情。 摘录
- 整数 6 。木制玩具球 将其放入 6 。
- 整数 3 。不要对木制玩具做任何事情。 摘录
- 整数 7 。木制玩具球 将其放入 2 。
- 整数 5 。木制玩具球 将其放入 1 。
- 最初,木制玩具如下图所示。在下图中,节点由箭头表示,球体编号由框架下标表示,球体中存储的整数由写入框架内的整数表示。
- 步骤 2 (整数 8 球体 将其放在 4 上后,木制玩具将如下图所示。
- 步骤 5 (整数 6 球体 将其放在 6 上后,木制玩具将如下图所示。
- 步骤 7 (整数 7 球体 将其放在 2 上后,木制玩具将如下图所示。
- 步骤 8 (整数 5 球体 将其放在 1 上后,木制玩具将如下图所示。
最终,每个球体中存储的整数的总价值是 5 + 7 + 5 + 8 + 5 + 6 + 4 = 40 ,这是最大可能值。
入力例2
6 21 5 5 5 5 5 1 2 1 3 1 4 1 5 1 6 5 8 8 8 8 8
出力例2
46