| 84 | } |
| 85 | |
| 86 | func NewTree(numbersVertex, root int, edges []TreeEdge) (tree *Tree) { |
| 87 | tree = new(Tree) |
| 88 | tree.numbersVertex, tree.root, tree.MAXLOG = numbersVertex, root, 0 |
| 89 | tree.depth = make([]int, numbersVertex) |
| 90 | tree.dad = make([]int, numbersVertex) |
| 91 | |
| 92 | for (1 << tree.MAXLOG) <= numbersVertex { |
| 93 | (tree.MAXLOG) += 1 |
| 94 | } |
| 95 | (tree.MAXLOG) += 1 |
| 96 | |
| 97 | tree.jump = make([][]int, tree.MAXLOG) |
| 98 | for j := 0; j < tree.MAXLOG; j++ { |
| 99 | tree.jump[j] = make([]int, numbersVertex) |
| 100 | } |
| 101 | |
| 102 | tree.edges = make([][]int, numbersVertex) |
| 103 | for _, e := range edges { |
| 104 | tree.addEdge(e.from, e.to) |
| 105 | } |
| 106 | |
| 107 | return tree |
| 108 | } |
| 109 | |
| 110 | // For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. |
| 111 | // Let's call `jump[j][u]` is the `2^j`-th ancestor above the node `u` with `u` in range `[0, numbersVertex)`, `j` in range `[0,MAXLOG)`. |