AT_arc029_4 [ARC029D] 高橋君と木のおもちゃ

给定一棵大小为 $N$，根为 $1$ 的树，并指定树上边的方向为编号大的指向编号小的。给定树上点 $i$ 的权值为 $s_i$。 现在给定 $M$ 个操作。每个操作依次进行。对于每个操作 $i$，有参数 $t_i$，可以选择： - 不进行操作 - 在树上任意选定一个节点 $u$ 。并对原树进行参数为 $t_i$ 的**上移操作**。 参数为 $t_i$ 的上移操作就是将原图中 $u$ 以及它的所有祖先（除了根）的权值向父亲节点上移一位（根节点权值被删除），然后再将 $s_u$ 设为 $t_i$。 求在经历 $M$ 次操作之后，最终整棵树的权值和最大是多少。

第一行一个整数 $N$，表示树的大小。 接下来 $N$ 行，每行一个整数 $s_i$，表示 $i$ 点的权值。 再接下来的 $N-1$ 行，每行两个整数 $a_i, b_i$，表示 $a_i$ 和 $b_i$ 之间有一条边。 第 $2N$ 行一个整数 $M$，表示操作的次数。 再接下来的 $M$ 行，每行一个整数 $t_i$。

一个整数，表示操作后整棵树的权值和的最大值。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 7 $ かつ $ M\ ≦\ 8 $ を満たすデータセット $ 1 $ に正解した場合は、$ 10 $ 点が与えられる。 - $ N\ ≦\ 16 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 20 $ 点が与えられる。 - 追加制約のないデータセット $ 3 $ に正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 1 以下の手順で操作を行います。 1. 整数 $ 2 $ を取り出す。木のおもちゃには何もしない。 2. 整数 $ 8 $ を取り出す。木のおもちゃの球 $ 4 $ に置く。 3. 整数 $ 1 $ を取り出す。木のおもちゃには何もしない。 4. 整数 $ 3 $ を取り出す。木のおもちゃには何もしない。 5. 整数 $ 6 $ を取り出す。木のおもちゃの球 $ 6 $ に置く。 6. 整数 $ 3 $ を取り出す。木のおもちゃには何もしない。 7. 整数 $ 7 $ を取り出す。木のおもちゃの球 $ 2 $ に置く。 8. 整数 $ 5 $ を取り出す。木のおもちゃの球 $ 1 $ に置く。 - 最初、木のおもちゃは下図のようになっています。以降数枚の図では、節を矢印で、球の番号を枠の添字で、球に格納されている整数は枠の内部に書かれた整数で表現されています。 !\[\](/img/arc/029/4-1.png) - ステップ $ 2 $ (整数 $ 8 $ を球 $ 4 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-2.png) - ステップ $ 5 $ (整数 $ 6 $ を球 $ 6 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-3.png) - ステップ $ 7 $ (整数 $ 7 $ を球 $ 2 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-4.png) - ステップ $ 8 $ (整数 $ 5 $ を球 $ 1 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-5.png) 最終的には、各球に格納されている整数の合計値は $ 5\ +\ 7\ +\ 5\ +\ 8\ +\ 5\ +\ 6\ +\ 4\ =\ 40 $ となり、これが考えられる最大値です。