https://yukicoder.me/problems/no/901 前提知識 LCA 解説 https://yukicoder.me/submissions/387110 この問題の上位互換であるが、本質的には同じ解法を使える。 与えられた頂点をEuler Tourでの順番にソートすると、(v1->v2の距離+v2->v3の距離+...+vN->v1…

https://yukicoder.me/problems/no/899 前提知識 オイラーツアー 解説 https://yukicoder.me/submissions/387104 操作を見ると、妖精がいる頂点数がどんどん減っている。 頂点を削減しながら、順番に見ていく的なことをしていくのかな… わからんとなったが… …

https://yukicoder.me/problems/no/900 前提知識 HL分解 遅延評価セグメントツリー(区間add,区間sum) 解説 https://yukicoder.me/submissions/387106 クエリを見ると部分木クエリとパスクエリになっている。 木に対して部分木もパスも行けるHL分解という手法…

https://yukicoder.me/problems/no/898 前提知識 LCA 解説 https://yukicoder.me/submissions/387102 頂点数が最小で連結な部分グラフを持ってくるが、 これはx-y, x-z, y-z間の最小パスで使われる頂点を集めたものになる。 これは直感的に分かるかもしれな…

https://yukicoder.me/problems/no/897 解説 https://yukicoder.me/submissions/386980 深さを最小化したいなら、なるべく子供をK個にするのがいい。 そうすると、密度が高まり、多くの頂点で深さを最小化できる。 あとは、計算だが、深さ基準で考えよう。 …