| 31 | void build(int r = 0) { |
| 32 | curloc = 0, csz(curhead = r), part(r); } |
| 33 | int lca(int u, int v) { |
| 34 | vi uat, vat; int res = -1; |
| 35 | while (u != -1) uat.push_back(u), u = parent[head[u]]; |
| 36 | while (v != -1) vat.push_back(v), v = parent[head[v]]; |
| 37 | u = (int)size(uat) - 1, v = (int)size(vat) - 1; |
| 38 | while (u >= 0 && v >= 0 && head[uat[u]] == head[vat[v]]) |
| 39 | res = (loc[uat[u]] < loc[vat[v]] ? uat[u] : vat[v]), |
| 40 | u--, v--; |
| 41 | return res; } |
| 42 | int query_upto(int u, int v) { int res = ID; |
| 43 | while (head[u] != head[v]) |
| 44 | res = f(res, values.query(loc[head[u]], loc[u]).x), |