i was tackling C. Experience the other day and had a "clever" idea (well it's perhaps the intended but whatever) to support all the queries mentioned in the problem in $$$O(\alpha(n))$$$, using both union by size/rank and path compression, i thought it was nice and didn't see it documented elsewhere so here it is, the idea is to basically notice that if we merge two teams (with union by size/rank ofc), we can set the experience of the child representative node to that of it self minus of it's parent representative experience, so basically:
now if we want the experience of B, we can traverse the tree up and sum, so $$$x-y+y = x$$$ and if we at some point added some value m to A, we'll have B equal x + A, and when path compression we'll just add experience of the recursion, let's describe what each dsu part will do:
sunion(a, b): regular union by size, but we set experience of the children representative to itself minus of it's parent
void sunion(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(size[a] > size[b]) {
parents[b] = a;
size[a] += size[b];
exp[b] -= exp[a];
}
else {
parents[a] = b;
size[b] += size[a];
exp[a] -= exp[a];
}
}
find(v): regular path compression, we go up the tree and move the link, but we add a twist that for each move up we sum the experience, code: (**incorrect code but the idea is there, can anyone help me figure out what's wrong? i spent two days on this :sob:**)
pair<int, int> find_backend(int v) {
if(v == parents[v]) return {v, exp[v]};
else {
parents[v] = find_backend(parents[v]).first;
exp[v] += find_backend(parents[v]).second;
return {parents[v], exp[v]};
}
}
int find(int v) {
return find_backend(v).first;
}
get_exp(v): and add_exp(v, m) both trivial
int get_exp(int v) {
return find_backend(v).second;
}
void add_exp(int v, int m) {
exp[find(v)] += m;
}
and yes that's it, we solved the problem in $$$O(\alpha(n))$$$! very cleanly, very nicely! i'd really appreciate some debugging help to make the code correct, sorry for my lack of implementation skills!
