• 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  };