PROBLEM LINK:Author: Minako Kojima DIFFICULTY:Hard PREREQUISITES:Link Cut Tree, HeavyLight Decomposition PROBLEM:Given a 0/1 colored tree of N nodes. Support two types operations (Q in total): 1. Ask the size of same color connected component of node u; 2. Toggle the color of node u. EXPLANATION:Both link cut tree and heavylight decomposition can solve this problem. Here we mainly talk about the later one. At the beginning, let me introduce the HeavyLight Decomposition (HLD). The basic idea is to decompose the tree into some links consisting of heavy edges and some separate light links, as following (2 links only): For each node, choose one of the biggest son as the heavy edge (choose anyone if there are some ties). This can ensure any path between two nodes in an Nnode tree will pass O(logN) links. With this property, if we maintain a segment tree or any other balanced binary search tree on each link, a lot of queries can be dealt. Suppose you have well known this data structure. Then, we try to apply HLD to this problem. First of all, let’s decompose the tree using HLD. Second, maintain the color and two values (the black/white subtree size rooted at this node assuming its color is black/white, despite what color it actually is) on each node u, denoted as Black[u] and White[u]. For each operation 1, starting from node u, we can upwardly find the lowest (with least depth, all nodes between them are same color) same color node and return the corresponding value stored. For each operation 2, assume u is changed to black from white. Upwardly find the first black node, denote as v. Then, subtract White[u] from White[middle], middle are all nodes between u and v (not including u). After that, the similar things happened to black side again: upwardly find the first white node, denote as v, add Black[u] to Black[middle], middle are all nodes between u and v (not including u). All steps introduced above can be supported by maintaining a Segment Tree on each links. For each operation, we can travel along different links upwardly and find the upmost same color node or the first different node. And for the subtraction/addition along the path, it could be done using the "segment cover" operation (with some values stored for the whole segment at segment tree nodes). Therefore, the time complexity can be controlled in O(Qlog^2N), here HLD contributes O(logN) and Segment Tree contributes for the other. If you have questions about the segment tree's operations, you'd better find some pure segment trees related problems and try to solve them. Because the key point of this problem is at HLD, we won't discuss the segment tree detailly here. AUTHOR'S AND TESTER'S SOLUTIONS:Solutions to be uploaded soon. Author's solution can be found here.
This question is marked "community wiki".
asked 16 Dec '13, 18:53

Here, the two key ideas are:
How many nodes in the substree rooted at $u$? This is a subtree information(And this is another problem called QTREE7). Instead of to update it directly it, you can update the information via update the path from $u$ to the root. And this is the basic lct operation. Similar idea was also be used on this problem.
Then suppose we have a node with degree $d$, one toggle operation can influence at most $d$ subtree, So the amortized time complexity is $O(nd + nlogn)$. To get a better time bound without $d$ as a factor, we use the following technologic so called "auxiliary nodes". That is, for each tree node $u$, we split it into 2 auxiliary nodes called $u_{black}$ and $u_{white}$, which are connected with all of its black children and white children respectively. If $p$ is the father of $u$, then if $u$ is white, we link $u_{white}$ to $p_{white}$, otherwise we link $u_{black}$ to $p_{black}$. Through this, we can process each toggle operation in 4 link/cut operations. For each query operation, remember the root's color actually is different from the subtree, so we access the 2nd nodes in the subtree to get the answer we need. Similar idea was also be used on IOI 2011 Day2 Elephants. answered 17 Dec '13, 03:14

And my solution in O(N sqrt(N)) remains undefeated: slowest AC solution :D I just process the queries in batches of around sqrt(N) at once; during those sqrt(N) queries, at most O(sqrt(N)) vertices of the tree can change colour, so there are at most O(sqrt(N)) nonleaf vertices. I compress the tree into connected components of the same colour (a vertex changing colour is alone in its component), construct the compressed tree, add edges that have at least one endpoint of changing colour, for every vertex precompute the sum of sizes of leaf components that are white/black, and BFS the compressed tree (without the obsolete leaves) for every query. answered 16 Dec '13, 20:14
Great to hear the different solutions :) Actually, this problem's test cases are a bit weak. Some optimized bruteforce solutions are also got accepted.
(16 Dec '13, 20:33)
1
@xellos0: Nice solution :) So, basically, for each batch of O(sqrt(N)) queries, you end up with a tree having O(sqrt(N)) vertices (after "compressing" all the leaves not corresponding to vertices changing colours into their parents). I really enjoy simpler O(sqrt(N))based alternative solutions to otherwise data structureintensive problems. "Sadly", this time my own solution is very much along the lines presented in the editorial. @shangjingbo: This solution is not bruteforce. I thought you (the organizers) were able to fail the bruteforce solutions by adding more test cases.
(16 Dec '13, 21:39)
@mugurelionut: There was one unusual bruteforce solution pass during contest(Thanks for @pat3ik), so there is a rejudge at the beginning. But as long as I relax my vigilance, there is still a bruteforce code with lots of heuristic optimization can pass the test data at the last day :( http://www.codechef.com/viewsolution/3101164
(17 Dec '13, 03:18)
@mugurelionut: I never said your solution was a bruteforce. :D
(17 Dec '13, 10:12)

It is my first time using HLD too, I am getting TLE though :/ Could anyone help me out? To find the lowest node with a specific color from the query node, I am walking upwards, and I keep a set to binary search in the heavy chains, if I find some node with the color I stop, otherwise I continue at the parent of the topmost node in that heavy chain. I am not sure if this is correct. My submission: http://www.codechef.com/viewsolution/3108467 Edit Nevermind, found a bug on my code haha :) Many thanks! answered 18 Dec '13, 02:19
can u explain what information each array u hv declared in ur solution is storing thanku...
(20 Dec '13, 10:49)
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..
(20 Dec '13, 19:46)
did u used 2D BIT for this?
(20 Dec '13, 22:34)
can u give a brief explanation how u will store the above tree shown in the editorial in the segment tree......
(21 Dec '13, 08:08)
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 viceversa for the black one).
(21 Dec '13, 18:16)
@brunoja what is the inverse array used for?
(29 Dec '13, 02:56)
showing 5 of 6
show all

First time I managed to use a heavy light decomposition. Felt like making an entire application to solve this. Key idea for my implementation is:  each node knows how many linked children of each color exist  query: find node's highest parent while color is the same and return it's value  update: update each node untill highest parent and first node with different color also how to N log N upperbound: heavy light decomposition where each heavy path is a presented as a fenwick tree. Inside each heavy path, we hold a fenwick tree, where the get(i) is higher then the get(j) if i is not in the same component as i. so we can just skip to the parent and on a heavy path do a binary seach for finding the right number. Pls check my code for doubts I learned to use this with this problem for the first time. answered 17 Dec '13, 06:15
Please clear this doubt: "update: update each node until highest parent and first node with different color also" here we have to find "the different color node" , how can we find efficiently that node without travelling the path that contain them?
(18 Dec '13, 18:25)
1
Going upwards the tree will visit at most logn light paths, and at most logn heavy chains, while in a heavy chain he uses that binary search idea to check if there is a different color node, if there isn't he skips the whole chain going to the topmost node. A chain can be very big, it is contain lots of nodes, so here you can't check nodes one by one. (that image in the editorial is quite confusing though :/)
(18 Dec '13, 18:36)
thank you for clearing my doubt.
(18 Dec '13, 19:36)
2
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. http://www.codechef.com/viewsolution/3060958 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.
(20 Dec '13, 05:37)

When will the solution by the tester and the setter be posted? answered 24 Dec '13, 16:11

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 answered 26 Dec '13, 14:39

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....
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??
What is segment cover operation?