競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやんLCA Lowest Common Ancestor 根付き木のある2頂点u,vの共通祖先で最も根から遠い頂点を高速に見つけること yukicoder上でのantaさんの解説 アルゴリズムはいくつかある「ダブリング」「HL分解」「RMQ使用」RMQが最速っぽいけど、体感HL分解の方が早いような… LCA＋根からある頂点への情報(深さとかコスト和とか)を使う解法が多い 例) 頂点aから頂点bへの距離はdist(根,a) + dist(根,b) - 2*dist(根,lca(a,b))となる LCAは単体では余り使われないので、これだけ知っててもしょうがなかったりするが、無いと解けない問題はある 根が変わる場合のLCA 問題 AOJ Lowest Common Ancestor ABC014 D.閉路 yukicoder No.898 tri-βutree 解説 yukicoder No.38
![競技プログラミングにおけるLCA問題まとめ [auxiliary tree] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/58f48f9f6495b1e4bfe5bf3fdc1cce218b4a6d9e/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F10328749687242644924%2F1583048158)
