← 返回题目列表

AtCoder · arc029_4

D. 高桥君和木制玩具

中文机器翻译题面 查看原题

問題文

高桥从他姐姐那里收到了一个木制玩具作为生日礼物。

木制玩具 N 球和 N-1 由一本书的各个部分组成。每个球都有 每个部分的编号最大为 1 从 N 。 编号至 1 从 N-1 。

N-1 本书的章节有所不同。 2 连接两个球体,所有球体的方向都是从编号较高的球体到编号较低的球体。还有,球 除 1 之外的每个球都有一个从该球指向另一个编号较小的球的节点。

每个球都准确无误 可以存储 1 整数。第一、球体 i (1 ≦ i≦ N) 是一个整数 s_i 已存储。

高桥和他的妹妹在场。 我决定使用 M 整数玩一个木制玩具游戏。

游戏的目标是使木制玩具每个球体中存储的整数之和尽可能大。

高桥君 M 次。

  1. 您手头的整数 1 拿出一个。i (1 ≦ i ≦ M) 第二步提取的整数为 t_i 。
  2. 执行以下操作之一:
  • 对木制玩具不做任何事情,整数 丢弃 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

请按照以下步骤操作。 摘录

  1. 整数 2 。不要对木制玩具做任何事情。 摘录
  2. 整数 8 。木制玩具球 将其放入 4 。
  3. 整数 1 。不要对木制玩具做任何事情。 摘录
  4. 整数 3 。不要对木制玩具做任何事情。 摘录
  5. 整数 6 。木制玩具球 将其放入 6 。
  6. 整数 3 。不要对木制玩具做任何事情。 摘录
  7. 整数 7 。木制玩具球 将其放入 2 。
  8. 整数 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