6/26 PKU - Algorithmer’s note

グラフが与えられる。最長で長さX以下の辺のみを用いて相互に到達できる２頂点の組の数を求めよ。

辺を長さでソートして、union-findを用いてその時々の答えの数を求める。最後に、クエリーごとに二分探索。

Bytelandには木構造状の道路がいくつかの町を結んでいる。あなたは町Kにいる。訪れたい町のリストが与えられるので、町Kから始まってその町をすべて通る旅行プランで、最も移動コストが短いもののコストを答えよ。

木DP。vector使うとTLEするのでlinked listを自前で書くといいかもしれない

辞書が与えられる。各クエリに対して、文字列が辞書に含まれるかどうか、さもなくばそれが辞書に含まれるある単語のミススペルかどうかを出力せよ。
ミススペルは、「１文字脱落」「１文字余計」「１文字別なものになった」「連続する２文字の順番が逆」のどれかである。

辞書をtrieに焼き直して、各クエリに対して元の文字列の候補をすべて作ってtrieで検索する