|
| 1 | +/** |
| 2 | + * Author: Adrito Mukherjee |
| 3 | + * Binary Lifting implementation in Javascript |
| 4 | + * Binary Lifting is a technique that is used to find the kth ancestor of a node in a rooted tree with N nodes |
| 5 | + * The technique requires preprocessing the tree in O(N log N) using dynamic programming |
| 6 | + * The techniqe can answer Q queries about kth ancestor of any node in O(Q log N) |
| 7 | + * It is faster than the naive algorithm that answers Q queries with complexity O(Q K) |
| 8 | + * It can be used to find Lowest Common Ancestor of two nodes in O(log N) |
| 9 | + * Tutorial on Binary Lifting: https://codeforces.com/blog/entry/100826 |
| 10 | + */ |
| 11 | + |
| 12 | +classBinaryLifting{ |
| 13 | +constructor(root,tree){ |
| 14 | +this.root=root |
| 15 | +this.connections=newMap() |
| 16 | +this.up=newMap()// up[node][i] stores the 2^i-th parent of node |
| 17 | +for(const[i,j]oftree){ |
| 18 | +this.addEdge(i,j) |
| 19 | +} |
| 20 | +this.log=Math.ceil(Math.log2(this.connections.size)) |
| 21 | +this.dfs(root,root) |
| 22 | +} |
| 23 | + |
| 24 | +addNode(node){ |
| 25 | +// Function to add a node to the tree (connection represented by set) |
| 26 | +this.connections.set(node,newSet()) |
| 27 | +} |
| 28 | + |
| 29 | +addEdge(node1,node2){ |
| 30 | +// Function to add an edge (adds the node too if they are not present in the tree) |
| 31 | +if(!this.connections.has(node1)){ |
| 32 | +this.addNode(node1) |
| 33 | +} |
| 34 | +if(!this.connections.has(node2)){ |
| 35 | +this.addNode(node2) |
| 36 | +} |
| 37 | +this.connections.get(node1).add(node2) |
| 38 | +this.connections.get(node2).add(node1) |
| 39 | +} |
| 40 | + |
| 41 | +dfs(node,parent){ |
| 42 | +// The dfs function calculates 2^i-th ancestor of all nodes for i ranging from 0 to this.log |
| 43 | +// We make use of the fact the two consecutive jumps of length 2^(i-1) make the total jump length 2^i |
| 44 | +this.up.set(node,newMap()) |
| 45 | +this.up.get(node).set(0,parent) |
| 46 | +for(leti=1;i<this.log;i++){ |
| 47 | +this.up |
| 48 | +.get(node) |
| 49 | +.set(i,this.up.get(this.up.get(node).get(i-1)).get(i-1)) |
| 50 | +} |
| 51 | +for(constchildofthis.connections.get(node)){ |
| 52 | +if(child!==parent)this.dfs(child,node) |
| 53 | +} |
| 54 | +} |
| 55 | + |
| 56 | +kthAncestor(node,k){ |
| 57 | +// if value of k is more than or equal to the number of total nodes, we return the root of the graph |
| 58 | +if(k>=this.connections.size){ |
| 59 | +returnthis.root |
| 60 | +} |
| 61 | +// if i-th bit is set in the binary representation of k, we jump from a node to its 2^i-th ancestor |
| 62 | +// so after checking all bits of k, we will have made jumps of total length k, in just log k steps |
| 63 | +for(leti=0;i<this.log;i++){ |
| 64 | +if(k&(1<<i)){ |
| 65 | +node=this.up.get(node).get(i) |
| 66 | +} |
| 67 | +} |
| 68 | +returnnode |
| 69 | +} |
| 70 | +} |
| 71 | + |
| 72 | +functionbinaryLifting(root,tree,queries){ |
| 73 | +constgraphObject=newBinaryLifting(root,tree) |
| 74 | +constancestors=[] |
| 75 | +for(const[node,k]ofqueries){ |
| 76 | +constancestor=graphObject.kthAncestor(node,k) |
| 77 | +ancestors.push(ancestor) |
| 78 | +} |
| 79 | +returnancestors |
| 80 | +} |
| 81 | + |
| 82 | +exportdefaultbinaryLifting |