nachinius / linkcuttrees

Apache License 2.0 GitHub

Link Cut Tree for fast path aggregation calculation on trees and graphs

Link Cut Trees

A collection of trees

with operations O(lg n) per operation (amortized)

maketree
link(v,w)
cut(v)
findroot(v)
pathaggregate(v)

Ref

[1] https://en.wikipedia.org/wiki/Link/cut_tree