perogram

LCA

No.898 tri-βutree ~LCA~

LCA

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

D - 閉路 abc014_4

Quiz https://atcoder.jp/contests/abc014/tasks/abc014_4 Submit https://atcoder.jp/contests/abc014/submissions/4325911 解法 どこかをrootにしてdfsでdepthを測っておく LCA (Lowest Common Ancestor)が高速に求まれば、depthの差から閉路の長さは求ま…