mayankp's blog

Edge aggregates for link-cut trees
By mayankp, history, 8 years ago, In English

How does one make a link-cut tree support finding the maximum (or anything else of the sort) along the edges of a vertex to the root? All implementations I have seen only support finding aggregates of vertices along such paths, and I think that simply having each vertex store the value of the edge from it to its parent doesn't work well when one links vertices which changes the parents of a bunch of vertices.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mayankp (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The trick is to treat edges as vertices : an edge (u,v) in your forest is represented by two edges in the link-cut tree : (u,e) and (e,v), with the edge information associated to the node e.

→ Reply