A. Vasya and Book
直接行く,$1$ を経由,$N$ を経由の 3 通りを調べる.
B. Vova and Trophies
二分探索で判定.
C. Multi-Subject Competition
それぞれソートして累積和.
D. Maximum Diameter Graph
次数 $2$ 以上にできる点をパス状に並べて,そこに葉を足していきます.
E. Increasing Frequency
$x=c-k$ を固定して解きます.$c$ にする $x$ の位置の左端・右端を決めたときの結果を式で表せば,適当な累積 max を使って計算できることが分かります.
F. Speed Dial
trie を作って根付き木の問題にしておきます.便宜上根も speed dial で来れる点だとしておきます.
$k$ 元集合頂点 $S$ を選び,$S$ を始点としたときの各文字列頂点へのコストの重み付き和を最適化する問題です.
$S$ に先祖子孫の関係ができる可能性を考慮しながら木 dp をします.ある部分根付き木では,最も近い先祖の点で $S$ に含まれるものの深さの値を仮定するごとの dp テーブルを計算するようにします.
G. Petya and Graph
カットの値として表現できます.
辺を選ぶならば頂点も選ぶという制約がありますが,これはそうしなかった場合に $-\infty$ の得点と見なせば,これはネットワークの容量 $\infty$ の辺として表現できます.