• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added lib/dataStructure/lca.cpp version [df81a86e707e972b]

            1  +//-------------------------------------------------------------
            2  +// The Least Common Ancestor
            3  +//
            4  +// Verified by
            5  +//   - ICPC 2021 Yokohama Regional I
            6  +//-------------------------------------------------------------
            7  +
            8  +
            9  +template<int K=17>
           10  +struct Lca
           11  +{
           12  + const int N;
           13  + const vector<int>& depth;
           14  + vector<vector<int>> jump;
           15  + Lca(int N, const vector<int>& parent, const vector<int>& depth)
           16  +  : N(N), depth(depth), jump(K, vector<int>(N, -1))
           17  + {
           18  +  jump[0] = parent;
           19  +  for(int k=0; k+1<K; ++k)
           20  +  for(int v=0; v<N; ++v)
           21  +   if(jump[k][v] != -1)
           22  +    jump[k+1][v] = jump[k][jump[k][v]];
           23  + }
           24  +
           25  + int operator()(int a, int b) const {
           26  +  if(depth[a]>depth[b]) swap(a,b);
           27  +  for(int k=0; k<K; ++k)
           28  +   if((depth[b]-depth[a]) & (1<<k))
           29  +    b = jump[k][b];
           30  +  if(a == b)
           31  +   return a;
           32  +  for(int k=K-1; k>=0; --k)
           33  +   if(jump[k][a] != jump[k][b]) {
           34  +    a = jump[k][a];
           35  +    b = jump[k][b];
           36  +   }
           37  +  return jump[0][a];
           38  + }
           39  +};