2022年07月24日 (日)[AtCoder] 精進。第２回PAST-O「可変全域木」。最小全域木に余分な辺を１本足して代わりに不要になった辺を取り除くと重みの和がどうなるか。まず、木に辺を１本足すと木はループを１つ持って木ではなくなる。不要になる辺はループを構成する辺のうちのどれか１本。追加した辺が頂点 A と B を結ぶなら、取り除ける辺は A と B のパス上の１辺。そのうち重みが最大のものを取り除けばいい。パス上の最大コストの１辺を効率良く探す方法は？ ダブリングで A と B の LCA までさかのぼるついでに見つけましょう。■提出 #33481914 (AC / 1107 Byte / 669 ms)。去年はまだ解けなかった>WA。これで第２回はコンプリート。第10回まであるなかで初のコンプリート。自分のすべての提出。