K - 巨大企業 / Conglomerate ～LCA～

ライブラリ LCA

Quiz https://atcoder.jp/contests/past201912-open/tasks/past201912_k AC https://atcoder.jp/contests/past201912-open/submissions/9277571 解法 LCA Code // LCA set VV G; const int N_MAX = 150010; const int MAX_LOG_V = 20; ll depth[N_MAX] = {};…

2019-10-05

No.898 tri-βutree ～LCA～

LCA

Quiz https://yukicoder.me/problems/no/898 Submission https://yukicoder.me/submissions/387090 解法 editorialの通り dijkstraとLCAの過去コードをコピーペーストその他全点間距離が必要？ワーシャルフロイド？制約的に無理・・・と思ったけれどLCAを…

2019-02-20

D - 閉路 abc014_4 ～木の深さを求めるdfs～

ライブラリダブリング LCA

Quiz https://atcoder.jp/contests/abc014/tasks/abc014_4 Submit https://atcoder.jp/contests/abc014/submissions/4325911 根が0決め打ちなので注意解法どこかをrootにしてdfsでdepthを測っておく LCA (Lowest Common Ancestor)が高速に求まれば、depth…