Bug of Euler Tour Tree

[MiSawa]

Challenge case

int main() {
  euler_tour_tree ETT;

  auto a = ETT.make_node(1 << 0);
  auto b = ETT.make_node(1 << 1);
  auto c = ETT.make_node(1 << 2);

  auto ba = ETT.link(b, a);
  auto ca = ETT.link(c, a);
  ETT.cut(ba);

  // Now components are {a, c} and {b}.
  // Since b is a singleton component, there should be no child.
  cout << b->ch[0] << " " << b->ch[1] << endl; // expects 0 0

  // Something undefined happens...
  auto ab = ETT.link(a, b);
  cout << ETT.sum_in_component(a) << endl; // expects 0b111
  return 0;
}

Cause

Here's the current implementation of cut operation.

algorithm/graph/euler_tour_tree.cc

Lines 99 to 103 in 4fdac82

	void cut(node *uv) {
	splay(uv); disconnect(uv,1); splay(uv->r);
	join(disconnect(uv,0), disconnect(uv->r,1));
	delete uv, uv->r;
	}

This implementation assumes that uv->r is in the right subtree of uv after splay(uv). This assumption is true right after link(u, v), but not maintained in the following operations.