And my solution in O(N sqrt(N)) remains undefeated: slowest AC solution
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)) non-leaf 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 pre-compute the sum of sizes of leaf components that are white/black, and BFS the compressed tree (without the obsolete leaves) for every query.
How can we augment the Link Cut tree to solve this problem ? I couldn’t figure out how to update the colour of a node efficiently using the path aggregate function.
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.
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.
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: CodeChef: Practical coding for everyone
In the Editorial it is written that “For each node, choose one of the biggest son as the heavy edge (choose anyone if there are some ties).” And on WIKI page it is written that “An edge from vertex parent(v) to v is called heavy if size(v) > 1/2*size(parent(v)) , and otherwise it is called light”.
Can anyone tell me whether we can implement in both the ways or they are implemented according to the problem.
Segment Trees are maintained for every links. Their sizes depend on the links’ lengths. For operations and queries, we may need to walk cross links and modify/query on these crossed segment trees.
The setter’s solution is based on LCT. And I think the similar ideas stated in the editorial can be also applied to LCT, maintaining two trees maybe. Just some quick ideas. Discussions are welcome.
@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 structure-intensive problems. “Sadly”, this time my own solution is very much along the lines presented in the editorial.
@shangjingbo: This solution is not brute-force. I thought you (the organizers) were able to fail the brute-force solutions by adding more test cases.
@mugurelionut: There was one unusual brute-force 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 brute-force code with lots of heuristic optimization can pass the test data at the last day CodeChef: Practical coding for everyone
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?
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 :/)
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.
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: 
