What HLD Cannot Do

What does a link/cut tree give you that heavy light decomposition does not?

A

Constant time LCA. HLD needs O(log⁡n)O(\log n) to climb between chain heads, while findroot and the LCA are O(1)O(1) in an LCT, so ancestor queries come free between updates.

B

The forest itself can change. HLD fixes the tree shape at build time, while link and cut are O(log⁡n)O(\log n) amortized in an LCT, so edges come and go between queries.

C

Path aggregates at all. HLD lays its chains out in DFS order, so it answers only subtree queries, while path queries are O(log⁡n)O(\log n) amortized in an LCT and come out of one splay tree.

D

A worst case bound. HLD costs O(log⁡2n)O(\log^2 n) amortized per path query, while link and cut are O(log⁡n)O(\log n) worst case in an LCT, so no single operation can spike.