I am learning link cut tree. I have seen the research paper and other slides.
But i have a question about this DS. Can LC Tree answer the number of childs under a root's subtree efficienty ? I mean, if I link root of a tree under a node, then if i ask the number of child under the great root, which is root of all the nodes. Can LC answer the question efficiently ? If yes, then how ? How can I propagate the value to all the ancestors ? I have seen one implementation here: 860934
How to modify it ?
Thanks in advance. :)
The link-cut trees solves problems in paths, you want know about the amount vertices in a subtree, for this you can use Euler Tour Tree that solves problems in components, and is very close to link-cut trees.
you are saying Euler tour than using segment tree to update a range, right ? But I need to update the value to all the ancestors of a node, but if i use euler tour + segment tree, it will update all the child under a node !! isn't it ?
i implement euler tour trees using Splay Trees, for the problem that you talk("amount of vertices in a component") is just return the size of a subtree.
then i need to learn splay tree too. :) Thanks.. another question.
Can this query be done for dynamic trees ? like adding a child or disconnecting a subtree !
Splay tree is a type of balanced BSTs that is used in link cut tree so you should learn splay trees before link cut trees after you learn link cut trees you will find answers to your questions
yes, splay trees are the heart of dinamic trees and you must learn it, not just for uses in dinamic trees with them you can solve many problems. if you implement Euler Tour trees using Segment Trees is just for static trees and you can't do dinamic operations like Link or Cut, for this you must uses a datastructure that allow this as Splay Trees. A example using just Splay Trees look this problem and my solution here.