Augmenting LinkCutTree doesn't seem to work

[tyilo]

I have tried to augment LinkCutTree with the subtree size, however I can't get it to work.

I have added int sz = 1; as a field to Node and modified Node::fix() to contain:

void fix() {
	sz = 1;
	if (c[0]) {
		c[0]->p = this;
		sz += c[0]->sz;
	}
	if (c[1]) {
		c[1]->p = this;
		sz += c[1]->sz;
	}
	// (+ update sum of subtree elements etc. if wanted)
}

My test code is

LinkCut T(4);
T.link(1, 0);
T.link(2, 1);
T.link(3, 0);

rep(i, 0, 4) {
	cout << i << " " << T.node[i].sz << "\n";
}

I would expect the output to be:

0 4
1 2
2 1
3 1

But instead I get:

0 2
1 1
2 1
3 1

The full code is available at https://gist.github.com/Tyilo/ebbbd06dcb02665c078ec3dac387c09a

[simonlindholm]

Ugh. I don't understand the link-cut tree well enough to say what's going wrong. We should replace it by a better version... (#63)

[Chillee]

In general, I think for data structures that can be augmented, like segtrees or (as we recently learned) Link Cut Trees, we should try to separate the code that's meant to be augmented from the rest of the code.

[Altynai]

@tyilo you might need to maintain the size of virtual children as well, see Benq's implementation: LCT.h#L27, example problem: https://codeforces.com/contest/1681/problem/F