{"provider_url":"https://hatena.blog","title":"\u7dda\u5f62\u6642\u9593 LCA","width":"100%","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Flinear_time_lca\" title=\"\u7dda\u5f62\u6642\u9593 LCA - AtCoderInfo\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","image_url":"https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738","published":"2026-04-10 14:12:10","height":"190","type":"rich","categories":["\u30b0\u30e9\u30d5\u7406\u8ad6","\u6728","\u30aa\u30a4\u30e9\u30fc\u30c4\u30a2\u30fc","LCA\uff08\u6700\u5c0f\u5171\u901a\u7956\u5148\uff09"],"blog_title":"AtCoderInfo","blog_url":"https://info.atcoder.jp/","author_name":"atcoder","author_url":"https://blog.hatena.ne.jp/atcoder/","provider_name":"Hatena Blog","url":"https://info.atcoder.jp/entry/algorithm_lectures/linear_time_lca","description":"1. \u6982\u8981 \u6839\u4ed8\u304d\u6728\u306b\u304a\u3051\u308b $2$ \u9802\u70b9 $u, v$ \u306b\u5bfe\u3057\u3066\uff0c $u$ \u304b\u3089 $v$ \u3078\u306e\u30d1\u30b9\u304c\u901a\u308b\uff0c\u6df1\u3055\u6700\u5c0f\u306e\u9802\u70b9\u3092 $u,v$ \u306e LCA \u3068\u3044\u3044\uff0c $\\mathrm{LCA}(u,v)$ \u3068\u66f8\u304d\u307e\u3059\uff0e LCA \u306e\u8a08\u7b97\u306b\u3064\u3044\u3066\u306f\uff0c\u30aa\u30a4\u30e9\u30fc\u30c4\u30a2\u30fc\u30c6\u30af\u30cb\u30c3\u30af \u306a\u3069\u3067\u3082\u89e6\u308c\u307e\u3057\u305f\uff0e\u672c\u8a18\u4e8b\u3067\u306f\u305d\u308c\u3088\u308a\u3082\u8a08\u7b97\u91cf\u30aa\u30fc\u30c0\u30fc\u306e\u826f\u3044\uff0cFarach-Colton \u3068 Bender \u306b\u3088\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u7d39\u4ecb\u3057\u307e\u3059\uff0e\u3053\u308c\u306f\uff0c $N$ \u9802\u70b9\u306e\u6728\u306b\u5bfe\u3057\u3066\uff0c $\\mathrm{O}(N)$ \u6642\u9593\u306e\u4e8b\u524d\u8a08\u7b97\u306e\u3082\u3068\uff0cLCA \u30af\u30a8\u30ea\u306b $\\mathrm{O}(1)$ \u6642\u9593\u3067\u7b54\u3048\u308b\u3082\u306e\u3067\uff0c\u3057\u305f\u304c\u3063\u3066\u8a08\u7b97\u91cf\u30aa\u30fc\u30c0\u30fc\u306f\u2026","version":"1.0"}