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

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の差から閉路の長さは求まる
• ダブリングで高速に親を辿れるように準備しておく

同じ深さになるまで片方を登らせる

• depthの差のビットを見れば使うべきジャンプが分かる
• ジャンプ：2^k個上の親までO(1)でたどること

その後、LCAの直前まで上がる

• LCAまで距離が50あるとしたら、32ジャンプ、16ジャンプ.. と詰めていく
• 64ジャンプでは飛び越えてしまう（親が同じになる）ので飛ばない

蟻本

• p274あたりにLCAとダブリングの解説がある

計算量

• bfsしているのでO(N)
  • 1回のみ
• 上記が1度構築できれば、
  • 1クエリ LCA(a, b)
  • の計算量は
  • ダブリングがあるため log(N)

BST (Binary Search Tree)上のLCA

• BSTの性質を活かすことでbfsは不要
• https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/
• 計算量は、hを木の高さとして O(h)

木の深さを求めるdfs

// 木の深さを求めるdfs
ll depth[300010];
void dfs(ll index, ll prev, ll _depth){
    depth[index] = _depth;
    
    auto list = G[index];
    for(ll to : list){
        if(to==prev){
            continue;
        }
        dfs(to, index, _depth+1);
    }
    return;
}
// 呼び出し側
// dfs(0, -1, 0);

類題

• K - 巨大企業 / Conglomerate
• https://atcoder.jp/contests/past201912-open/tasks/past201912_k
• https://atcoder.jp/contests/past201912-open/submissions/9277571
• 根を可変にしたのとバグも1つ取れたはず