Pick The Dynamic Tree

A forest changes over time: link, cut, and after each change a query for the sum of values on the path from uu to vv. Queries are online. What do you build?

A

A rollback DSU over time. Paths are exactly what its union structure aggregates, and link and cut are O(log⁡n)O(\log n) amortized.

B

A link/cut tree. Paths are exactly what preferred paths aggregate, and link and cut are O(log⁡n)O(\log n) amortized.

C

Heavy light decomposition. Paths are exactly what its chains aggregate, and link and cut cost O(log⁡n)O(\log n) per rebuild.

D

An Euler tour tree. Paths are exactly what a difference of two tour prefixes gives, and link and cut are O(log⁡n)O(\log n).