QTREE6 - Editorial

editorial
, , , ,
21

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ā€¦

22

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.

23

did u used 2-D BIT for this?

24

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

25

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ā€¦

26

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).

27

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

28

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

29

When will the solution by the tester and the setter be posted?

30

can anyone tell me where my code is failing.I hv test all the cases and it is giving correct answerā€¦solution link http://www.codechef.com/viewsolution/3144480

31

@brunoja what is the inverse array used for?

32

What is segment cover operation?

33

@brunoja could you explain your solution.what all variable names you have used and what they mean?

34

You can choose ties in any way.