{"id":1557,"date":"2021-01-14T14:05:48","date_gmt":"2021-01-14T22:05:48","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1557"},"modified":"2021-12-18T19:14:33","modified_gmt":"2021-12-19T03:14:33","slug":"lca-binary-lifting-template","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/01\/14\/lca-binary-lifting-template\/","title":{"rendered":"LCA (Binary Lifting) Template"},"content":{"rendered":"\n
class Lca {\npublic:\n  \/\/ 2^10 = 1024\n  \/\/ 2^14 > 10'005\n  static constexpr int kMaxN = 50'005;\n  static constexpr int kMaxP = 17;\n\n  Lca (TreeNode* root) {\n    node_to_index[nullptr] = 0;\n    \/\/ index & depth starts from 1\n    int index = 1;\n    GetDepth(root, 1, nullptr, index);\n    n = index;\n    \n    \/\/ node: [1, n]\n    memset(alg, 0, sizeof(alg));\n    for (int i = 1; i <= n; ++i) {\n      alg[i][0] = parent[i];\n    }\n    \n    \/\/ i's 2^j father = i's 2^(j-1) father's 2^(j-1) father\n    \/\/ alg[i][j] = alg[alg[i][j-1]][j-1]\n    for (int j = 1; j <= kMaxP; ++j) {\n      for (int i = 1; i <= n; ++i) {\n        alg[i][j] = alg[alg[i][j-1]][j-1];\n      }\n    }\n  }\n  \n\/\/   Lca (vector<int> const& parent_input) {\n\/\/     n = parent_input.size();\n\/\/     memcpy(parent, parent_input.data(), n * sizeof(int));\n\/\/     \/\/ node: [1, n]\n\/\/     memset(alg, 0, sizeof(alg));\n\/\/     for (int i = 0; i < n; ++i) {\n\/\/       alg[i + 1][0] = parent[i];\n\/\/     }\n    \n\/\/     \/\/ i's 2^j father = i's 2^(j-1) father's 2^(j-1) father\n\/\/     \/\/ alg[i][j] = alg[alg[i][j-1]][j-1]\n\/\/     for (int j = 1; j <= kMaxP; ++j) {\n\/\/       for (int i = 1; i <= n; ++i) {\n\/\/         alg[i][j] = alg[alg[i][j-1]][j-1];\n\/\/       }\n\/\/     }\n\/\/   }\n  \n\/\/   int GetKParent(int i, int k) {\n\/\/     for (int j = kMaxP; j >= 0 && k >= 1; --j) {\n\/\/       if (k == (1 << j)) {\n\/\/         return alg[i][j];\n\/\/       }\n\/\/       if (k > (1 << j)) {\n\/\/         k -= (1 << j);\n\/\/         i = alg[i][j];\n\/\/       }\n\/\/     }\n\/\/     return 0;\n\/\/   }\n  \n  int GetLca(int root0, int root1) {\n    if (depth[root0] < depth[root1]) {\n      swap(root0, root1);\n    }\n    \/\/ keep jump untill root0 and root1 is at the same level\n    for (int j = kMaxP; j >= 0; --j) {\n      if (depth[alg[root0][j]] >= depth[root1]) {\n        root0 = alg[root0][j];\n      }\n    }\n    if (root0 == root1) {\n      return root0;\n    }\n    \/\/ keep jump untill root0 and root1 has the same father\n    for (int j = kMaxP; j >= 0; --j) {\n      if (alg[root0][j] != 0 && alg[root0][j] != alg[root1][j]) {\n        root0 = alg[root0][j];\n        root1 = alg[root1][j];\n      }\n    }\n    return alg[root0][0];\n  }\n  \n  TreeNode* GetLca(TreeNode* root0, TreeNode* root1) {\n    return index_to_node[GetLca(node_to_index[root0], node_to_index[root1])];\n  }\n  \n  \/\/ Returns the distance between a node and its one parent\n  int GetDistance(int root, int parent) {\n    int res = 0;\n    for (int j = kMaxP; j >= 0; --j) {\n      if (depth[alg[root][j]] >= depth[parent]) {\n        root = alg[root][j];\n        res += 1 << j;\n      }\n    }\n    return res;\n  }\n  \n  int GetDistance(TreeNode* root, TreeNode* parent) {\n    return GetDistance(node_to_index[root], node_to_index[parent]);\n  }\n  \nprivate:\n  int n;\n  \n  static unordered_map<TreeNode*, int> node_to_index;\n  static unordered_map<int, TreeNode*> index_to_node;\n  \n  static int depth[kMaxN];\n  static int parent[kMaxN];\n  \n  \/\/ i's 2^j father\n  static int alg[kMaxN][kMaxP + 1];\n  \n  void GetDepth(TreeNode* root, int curr_depth, TreeNode* father, int &index) {\n    if (root == nullptr) {\n      return;\n    }\n    node_to_index[root] = index;\n    index_to_node[index] = root;\n    depth[index] = curr_depth;\n    parent[index] = node_to_index[father];\n    index++;\n    GetDepth(root->left, curr_depth + 1, root, index);\n    GetDepth(root->right, curr_depth + 1, root, index);\n  }\n};\n\n\nint Lca::alg[kMaxN][kMaxP + 1];\nint Lca::depth[kMaxN];\nint Lca::parent[kMaxN];\nunordered_map<TreeNode*, int> Lca::node_to_index;\nunordered_map<int, TreeNode*> Lca::index_to_node;<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,66],"tags":[],"class_list":["post-1557","post","type-post","status-publish","format-standard","hentry","category-alg","category-graph-alg"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1557","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1557"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1557\/revisions"}],"predecessor-version":[{"id":1573,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1557\/revisions\/1573"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1557"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1557"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1557"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}