| 9 | jmp[i] = jmp[i-1]->jmp[i-1]; } }; |
| 10 | node* st[100000]; |
| 11 | node* lca(node *a, node *b) { |
| 12 | if (!a || !b) return NULL; |
| 13 | if (a->depth < b->depth) swap(a,b); |
| 14 | for (int j = 19; j >= 0; j--) |
| 15 | while (a->depth - (1<<j) >= b->depth) a = a->jmp[j]; |
| 16 | if (a == b) return a; |
| 17 | for (int j = 19; j >= 0; j--) |
| 18 | while (a->depth >= (1<<j) && a->jmp[j] != b->jmp[j]) |
| 19 | a = a->jmp[j], b = b->jmp[j]; |
| 20 | return a->p; } |
| 21 | // vim: cc=60 ts=2 sts=2 sw=2: |