I have been studying link cut trees nowadays but don't seem to figure out how to find the kth ancestor of a particular node. Can this be done? If yes then how?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
I have been studying link cut trees nowadays but don't seem to figure out how to find the kth ancestor of a particular node. Can this be done? If yes then how?
Name |
---|
Can you find the kth ancestor in a splay tree? A link-cut tree is just a splay tree.
i do not understand. well yes it is just a splay tree, but how to get the kth ancestor query along with link/cut queries supported?
can you please be clear about whether it can be done or not?
when you're asked for kth ancestor of node V:
Store in each node the size of its subtree (in the splay tree not the original tree)
Access V
Now there should be >= K nodes to the left of node V, go to the left child of V and use sub tree sizes to find kth node from the right
How to do it:
Let's say you have L nodes to left and R nodes to the right
if R == K-1: current node is the kth ancestor
if R > K-1: kth ancestor is in right subtree
if R < K-1: kth ancestor is in left subtree, when you go left, you're objective changes to finding the (K — R — 1)th node (as K nodes from the right and root node were discarded)
In case the root was fixed, you can just do dfs from the root and use a stack to keep track of all ancestors, when you get to Node V, the answer is in stack[size — K]
kth ancestor is not the same as the kth element in an ordered sequence.
Not the kth node in the whole tree, I meant the kth in left subtree from the right as they are keyed by depth
hmm what you say seems correct...are you sure about it?
Yes
Assuming all nodes are connected, access(v) will place v in the same preferred path as the root node, since all nodes in the path are keyed by depth and (usually) stored in a splay tree, splaying v will leave all its ancestors in the left subtree
I personally don't suggest using linkcut tree unless necessary, if you can get by just dfs and a stack, it will be much faster and easier to code and debug
and how would you maintain the size of subtree, after a cut and link operation alot of data has to be changed? do all the operations still remain logn??