QTREE6 - Editorial

what @brunoja says… note that I used 3 BITs per path. One to see the component the node in the path connects to. just a number which is the same if two nodes are in the same component (same color and connected).
And 1 tree per color. CodeChef: Practical coding for everyone

I also want to remind the Java people that there is a stacklimit, so I had to rewrite my methods which used to many recursion.

2 Likes

can u explain what information each array u hv declared in ur solution is storing thanku…

There won’t be ties (please someone correct me if I am wrong…). For instance let’s say that the size of a node ‘v’ is N, and N is even. The children will sum up to N-1 nodes. Pick one child ‘c’ with size© > size(v)/2, it means that size© is at least N/2+1, which makes it impossible for another child to have its size bigger than size(v)/2. The same applies for an odd N with similar analysis. Just make some real examples on paper and it will be clear :slight_smile:

num is the node number, which I name with the dfs func; inv is the inverse of the num array; wei is the size of each node; hev tells which heavy chain the node is in (or none); top contains the topmost node of a heavy chain; pai is the parent of the node; seg is the BIT that is used in the described solutions (although I am not sure if its 100% the same approach in the editorial); col is the current color of the node; dep is the highest node number of the tree rooted at a node; fio contains the child of a node in a heavy chain. I hope it is clear :), just tell me if something else is obscure…

if we decide heavy and light edges according to the editorial that the edge to the son with biggest size is heavy , then there are chances of tie , when a node v has some sons and two or more have biggest size for example a node ha sthree childrens and of them has size 5 and one has size 3.then u can consider any of the two edges of size 5 as heavy.
but if u consider a node v having size(v)>1/2xsize(parent(v)) . Then there will be no tie.

did u used 2-D BIT for this?

can u give a brief explanation how u will store the above tree shown in the editorial in the segment tree…

Do we move upwardly node by node to find the upmost same color node…plz clarify how we will move if the edge is heavy and when the edge is light.THANKYOU…

The BIT is 1D, and it is for the entire tree. The only thing I store from the tree in the editorial is wether a node belongs to a heavy chain or not, and for each chain I keep the index of the nodes of black color (for the white tree, and vice-versa for the black one).

I have confusion in binary search what type of array we will keep to find the same color node in a heavy chain by binary search please explain.THANKYOU

plzzz explain how to find the most nearby ancestor of different color by binary search??

@brunoja what is the inverse array used for?

What is segment cover operation?

You can choose ties in any way.