| 2 | #include "../code/data-structures/segment_tree.cpp" |
| 3 | |
| 4 | int lca_slow(int n, int *ps, int a, int b) { |
| 5 | vi as, bs; |
| 6 | while (a != -1) { |
| 7 | as.push_back(a); |
| 8 | a = ps[a]; |
| 9 | } |
| 10 | |
| 11 | while (b != -1) { |
| 12 | bs.push_back(b); |
| 13 | b = ps[b]; |
| 14 | } |
| 15 | |
| 16 | reverse(as.begin(), as.end()); |
| 17 | reverse(bs.begin(), bs.end()); |
| 18 | |
| 19 | int at = 0; |
| 20 | while (at+1 < size(as) && at+1 < size(bs) && as[at+1] == bs[at+1]) { |
| 21 | at++; |
| 22 | } |
| 23 | |
| 24 | return as[at]; |
| 25 | } |
| 26 | |
| 27 | int* pars(int n, vi *adj) { |
| 28 | int *res = new int[n]; |