Graph Theory37 sections · 1633 units
Open in Course

Debugging Rerooting (Common mistakes)

(Double-counting)

The most common bug is double-counting. When computing up[v], you must exclude vv's own contribution from down[u]. If you forget, vv's subtree gets counted twice in the final answer.

Second common bug: wrong root initialization. The root has no parent, so up[root] = 0. If you skip this or initialize it incorrectly, errors propagate to every node.

Third common bug: confusing node indices. If your tree is 11-indexed but your arrays are 00-indexed, off-by-one errors corrupt the results. Pick one convention and stick to it. Print intermediate values (downdown, sizesize, upup) for a small tree and verify by hand.