noshi91 https://blog.hatena.ne.jp/noshi91/ noshi91のメモ https://noshi91.hatenablog.com/ アルゴリズム 概要 シンプルなアルゴリズムですが、Level Ancestor Problem 自体の知名度が低そうなので宣伝を兼ねて紹介します。 Level Ancestor Level Ancestor とは、根付き木について定義される概念です。 の祖先であって、深さが であるもの ( の深さ ) の深さが分かれば「 から根の方向に 回親を辿った頂点は何か」というクエリを Level Ancestor を求める問題に帰着できます。 逆もまた帰着可能なので、多くの状況でこれらは同一の問題とみなすことが出来ます。 アルゴリズム 頂点の根付き木と 個のクエリ が与えられたとき、全てのクエリの結果を で得るアル… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnoshi91.hatenablog.com%2Fentry%2F2019%2F09%2F22%2F114149" title="Offline Level Ancestor Θ(N+Q) - noshi91のメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/noshi91/20190922/20190922114110.png Hatena Blog https://hatena.blog 2019-09-22 11:41:49 rich https://noshi91.hatenablog.com/entry/2019/09/22/114149 1.0 100%