{"id":1363,"date":"2020-06-21T16:02:33","date_gmt":"2020-06-21T23:02:33","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1363"},"modified":"2020-06-29T22:11:38","modified_gmt":"2020-06-30T05:11:38","slug":"lowest-common-ancestor-concepts","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/06\/21\/lowest-common-ancestor-concepts\/","title":{"rendered":"Lowest Common Ancestor"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>Lowest Common Ancestor (LCA) is a typical rooted tree related problem. <\/p>\n\n\n\n<p>A simple solution is use <code>dfs<\/code> to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same  subtree, the current node is the LCA. The solution costs <code>O(n)<\/code> time. <\/p>\n\n\n\n<p>If we need to support a list of queries. The simple solution is not good anymore. A technique we could use here is the <strong>Binary Lifting<\/strong> method.<\/p>\n\n\n\n<p><strong>Binary Lifting<\/strong> is actually a Dynamic Programming technique. We define <code>alg[i][k]<\/code> as the <code>2^k th<\/code> parent of node <code>i<\/code>.<\/p>\n\n\n\n<p>Since <code>2^k=2^(k-1)+2^(k-1)<\/code>, we have <code>alg[i][k]=alg[alg[i][k-1]][k-1]<\/code>.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">constexpr int MAX = 31; \/\/ 2^31 nodes\n\n\/\/ alg[i][0] = parent[i]\nfor (int i = 0; i &lt; n; ++i) {\n    alg[i][0] = parent[i];\n}\n\n\/\/ 2^k = 2^k-1 + 2^k-1\n\/\/ alg[i][k] = alg[alg[i][k-1]][k - 1]\nfor (int k = 1; k &lt; MAX; ++k) {\n    for (int i = 0; i &lt; n; ++i) {\n        if (alg[i][k - 1] != -1) {\n            alg[i][k] = alg[alg[i][k - 1]][k - 1];\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">The Kth Parent of a Node<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">int getKthAncestor(int node, int j) {\n    for (int k = MAX; k >= 0; --k) {\n        if (node != -1 &amp;&amp; j >= (1 &lt;&lt; k)) {\n            j -= (1 &lt;&lt; k);\n            node = alg[node][k];\n        }\n    }\n    return node != -1? node : -1;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time&#8230;.<\/p>\n","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-1363","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\/1363","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=1363"}],"version-history":[{"count":4,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1363\/revisions"}],"predecessor-version":[{"id":1406,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1363\/revisions\/1406"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1363"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1363"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}