問題文

N 個の要素が一列に並んでいます。これらの要素をいくつかの区間に分割したいとします。各区間 [l, r) には、スコア c_{l, r} が付いているものとします。

K を N 以下の正の整数として、K + 1 個の整数 t_0, t_1, \dots, t_K を、0 = t_0 \lt t_1 \lt \dots \lt t_K = N を満たすようにとり、N 個の要素を K 個の区間 [t_0, t_1), [t_1, t_2), \dots, [t_{K-1}, t_K) に分割します。このとき、この区間分割のスコアを次のように定めます。

• c_{t_0, t_1} + c_{t_1, t_2} + \dots + c_{t_{K-1}, t_K}

区間分割の仕方をすべて考えたときの、考えられるスコアの最小値を求めてください。なお、区間の個数 K についても自由に選択できるものとします。

入力例

3
0 7 1 6
7 0 5 3
1 5 0 4
6 3 4 0

出力例

5

3 つの要素を、「最初の 2 個」と「最後の 1 個」の 2 つの区間に分割するのが最適です。このときのスコアは

• 最初の 2 個の要素からなる区間：1
• 最後の 1 個の要素からなる区間：4

を合計したものであり、1 + 4 = 5 です。

問題文

長さが M の文字列 S と、長さが N の文字列 T が与えられます。

S に以下の 3 通りの操作を繰り返し施すことで、T に変換したいとします。そのような一連の操作のうち、操作回数の最小値を求めてください。なお。この最小値のことを文字列 S, T の編集距離と呼びます。

• 変更：文字列 S 中の文字を 1 つ選んで任意の文字に変更する
• 削除：文字列 S 中の文字を 1 つ選んで削除する
• 挿入：文字列 S の好きな箇所に好きな文字を 1 文字挿入する

入力例

5 6
abcde
bcdefg

出力例

3

文字列 S から先頭 1 文字 "a" を削除して、末尾に 2 文字 "fg" を付け加えることで T に一致します。よって、求める編集距離は 1 + 2 = 3 です。

問題文

頂点数 N の木が与えられます。 各頂点は 1, 2, \dots, N と番号付けされていて、 i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

この木において、頂点 1 を根とします。このとき、各頂点を根とした根付き木の大きさを求めてください。

入力例

4
1 2
1 3
3 4

出力例

4
1
2
1

問題文

1 から N のついた N 個の頂点からなる、頂点 1 を根とする木が与えられます。辺は N-1 個あり、i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

クエリが Q 回与えられるので、処理してください。i 番目のクエリでは u_i, v_i が与えられるので、u_i と v_i の「最小共通祖先」、すなわち u_i の祖先でも v_i の祖先でもあるものであって、深さが最も深い頂点 p の番号を出力します。

ここで、頂点 x の「祖先」とは、x から根まで親方向にたどったときに通る頂点の集合であり、頂点 x や根も x の祖先に含みます。また、頂点 x の「深さ」とは、x から根まで到達するときに通る辺の個数の最小値とします。根の深さは 0 です。

入力例

6
1 2
1 3
2 4
3 5
3 6
3
4 6
5 6
1 5

出力例

1
3
1

• 頂点 1 は、頂点 4 の祖先でも頂点 6 の祖先でもある唯一の頂点です。よって、頂点 4, 6 の最小共通祖先は頂点 1 です。
• 頂点 5 の祖先でも頂点 6 の祖先でもある頂点は頂点 1, 3 の 2 つがありますが、その中で深さが最も深いものは頂点 3 です。よって、頂点 5, 6 の最小共通祖先は頂点 3 です。
• 頂点 1 は、頂点 1 の祖先でも頂点 5 の祖先でもある唯一の頂点です。よって、頂点 1, 5 の最小共通祖先は頂点 1 です。「頂点 x は頂点 x の祖先である」ことに注意してください。

問題文

V個の街があります。各街には1,2,...,Vと番号が付いています。E本の水道管があり、i本目の水道管は街u_iから街v_iへ水を最大でc_iだけ流すことが出来ます。街1から街Vへ流せる水の量の最大値を求めてください。

入力例

5 7
1 2 8
1 3 10
2 4 5
2 5 5
3 2 9
3 4 6
4 5 12

出力例

16

問題文

V個の街があります。各街には1,2,...,Vと番号が付いています。E本の水道管があり、i本目の水道管は街u_iから街v_iへ水を最大でc_iだけ流すことができますが、水を1流すごとに費用がd_iかかります。街1から街Vへ水をFだけ流すとき、合計費用の最小値を求めてください。

入力例

6 9 3
1 2 3 2
1 3 2 1
2 3 2 2
2 4 3 4
3 4 5 1
3 5 6 2
4 5 2 2
4 6 6 3
5 6 10 2

出力例

18

問題文

長さ N の整数列 A = (a_0, a_1, \ldots, a_{N-1}) があります。

あなたは今からこの数列について Q 個のクエリを処理します。i 番目のクエリでは、T_i, X_i, Y_i が与えられるので、以下の処理してください。

• T_i = 1 のとき: a_{X_i} を Y_i で置き換える
• T_i = 2 のとき: \min \left( a_{X_i}, a_{X_i + 1}, \ldots , a_{Y_i - 1} \right) を出力する

入力例

6 4
1 6 3 7 2 5
2 1 5
1 4 8
2 1 5
2 3 6

出力例

2
3
5

• 1 個目のクエリでは、\min(a_1, a_2, a_3, a_4) = \min(6, 3, 7, 2) = 2 を出力します。
• 2 個目のクエリでは、a_4 が 8 に書き換えられ、A = (1, 6, 3, 7, 8, 5) という数列に変化します。
• 3 個目のクエリでは、\min(a_1, a_2, a_3, a_4) = \min(6, 3, 7, 8) = 3 を出力します。
• 4 個目のクエリでは、\min(a_3, a_4, a_5) = \min(7, 8, 5) = 5 を出力します。

問題文

長さ N の数列 A = (a_0, a_1, \ldots, a_{N-1}) があります。Q 個のクエリが与えられるので、これらを順に処理してください。

• クエリ 1: l, r, x が与えられるので、a_l, a_{l+1}, \ldots, a_{r-1} に x を足す
• クエリ 2: l, r が与えられるので、\min( a_l, a_{l+1}, \ldots, a_{r-1} ) を求める

入力例

6
5 1 8 2 1 5
3
2 0 4
1 1 4 5
2 0 3

出力例

1
5

• 1 個目のクエリでは、\min(a_0, a_1, a_2, a_3) = \min(5, 1, 8, 2) = 1 を出力します。
• 2 個目のクエリでは、a_1, a_2, a_3 それぞれに 5 を足します。これにより、数列は A = (5, 6, 13, 7, 1, 5) に変化します。
• 3 個目のクエリでは、\min(a_0, a_1, a_2) = \min(5, 6, 13) = 5 を出力します。