[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$。
**【输出格式】**
一个整数,表示操作后整棵树的权值和的最大值。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc029/tasks/arc029_4
高橋君は妹から誕生日プレゼントに木のおもちゃを貰った。
木のおもちゃは $ 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 $ を取り出すことを表す。
输出格式
最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を $ 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
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
说明
### 部分点
この問題には部分点が設定されている。
- $ 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 $ となり、これが考えられる最大値です。