题意:动态给点连边 询问两个点之间最早是在第几个操作连起来的
题解:因为并查集按秩合并 秩最高是logn的 所以我们可以考虑把秩看作深度 跑LCA
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 5; int n, m, cnt; int fa[MAXN]; int id[MAXN]; int zhi[MAXN]; int find(int x) { if(fa[x]) return find(fa[x]); else return x; } int ffind(int x) { if(fa[x]) return ffind(fa[x]) + 1; else return 0; } void add(int x, int y, int z) { int fx = find(x); int fy = find(y); if(fx != fy) { if(zhi[fx] < zhi[fy]) { fa[fx] = fy; id[fx] = z; } else fa[fy] = fx, id[fy] = z; if(zhi[fx] == zhi[fy]) zhi[fx]++; } } int query(int x, int y) { int fx = find(x); int fy = find(y); if(fx != fy) return 0; int dx = ffind(x), dy = ffind(y); int res = 0; while(dx > dy) res = max(res, id[x]), x = fa[x], dx--; while(dx < dy) res = max(res, id[y]), y = fa[y], dy--; while(x != y) { res = max(res, max(id[x], id[y])); x = fa[x]; y = fa[y]; } return res; } int main() { cnt = 0; scanf("%d%d", &n, &m); int las = 0; for(int i = 1; i <= m; i++) { int opt, u, v; scanf("%d%d%d", &opt, &u, &v); u ^= las, v ^= las; if(opt) printf("%d\n", las = query(u, v)); else add(u, v, ++cnt); } return 0; }View Code