記事の最適化 C#編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
n 個の記事があり、それぞれの記事には 1 から n までの番号が振られています。
また、それぞれの記事 i には評価 a_i が設定されています。
さらに、n 個の記事番号の組 u_i, v_i が与えられます。これは、記事 u_i と記事 v_i が互いに関連項目になっていることを表します。
ここで、与えられた関連関係を双方向の 2 つの辺とする有向グラフを考え、この中から n - 1 本の辺を持つ根付き木を取り出すことを考えます。
そのような根付き木のうち、以下の条件を満たすように k = 1, 2, ..., n 個の記事を選ぶとき、その評価の合計の最大値の列が辞書順最大になるようなものを 1 つ求め、その列を出力してください。
・ 記事 1 ~ 記事 n の中から異なる k 個の記事を選ぶ
・ すべての選んだ記事について、親の記事が存在するなら必ず親の記事も選んでいる
- 入力される値
-
n
a_1 a_2 ... a_n
u_1 v_1
u_2 v_2
...
u_n v_n
・ 1 行目には、記事の数 n と長さの合計の上限を表す整数 k が半角スペース区切りで入力されます。
・ 2 行目には、記事 i の評価 a_i が半角スペース区切りで入力されます。
・ 続く n 行 (1 ≦ i ≦ n) には、記事 u_i と記事 v_i が半角スペース区切りで入力されます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
i 行目に、評価の合計の最大値が辞書順最大になるような根付き木を取り出した場合の、k = i のときの評価の合計の最大値の列を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200
・ 1 ≦ a_i ≦ 1000000000 = 10^9 (1 ≦ i ≦ n)
・ 1 ≦ u_i, v_i ≦ n (1 ≦ i ≦ n)
・ a_i ≠ a_j (1 ≦ i < j ≦ n)
・ u_i ≠ v_i (1 ≦ i ≦ n)
・ (u_i, v_i) ≠ (u_j, v_j) かつ (u_i, v_i) ≠ (v_j, u_j) (1 ≦ i < j ≦ n)
・ 与えられるグラフは連結である
- 入力例1
-
5
1 10 100 1000 10000
5 3
3 2
2 4
4 1
1 5
- 出力例1
-
10000
10100
11001
11101
11111
- 入力例2
-
5
10000 100 1 1000 10
1 2
2 3
3 4
4 5
3 5
- 出力例2
-
10000
10100
10101
11101
11111
