| 30 | } |
| 31 | |
| 32 | int lca(int u, int v) { |
| 33 | vi uat, vat; int res = -1; |
| 34 | while (u != -1) uat.push_back(u), u = parent[u].first; |
| 35 | while (v != -1) vat.push_back(v), v = parent[v].first; |
| 36 | u = (int)size(uat) - 1, v = (int)size(vat) - 1; |
| 37 | while (u >= 0 && v >= 0 && uat[u] == vat[v]) |
| 38 | res = uat[u], u--, v--; |
| 39 | return res; |
| 40 | } |
| 41 | |
| 42 | // int query_upto(int u, int v) { |
| 43 |