QTREE6 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Minako Kojima
Tester: Gerald Agapov
Editorialist: Jingbo Shang

DIFFICULTY:

Hard

PREREQUISITES:

Link Cut Tree, Heavy-Light 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 heavy-light decomposition can solve this problem. Here we mainly talk about the later one.

At the beginning, let me introduce the Heavy-Light 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 N-node 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 sub-tree 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.
Tester’s solution can be found [here][10].

[9]:
[10]: https://www.codechef.com/download/Solutions/2013/December/Tester1/QTREE6.cpp

5 Likes
2

Can you please explain how segment tree can be used to store the given tree or give a link explaining it.

3

And my solution in O(N sqrt(N)) remains undefeated: slowest AC solution :smiley:

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.

3 Likes
4

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.

5

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.

6

Great to hear the different solutions :slight_smile:
Actually, this problem’s test cases are a bit weak. Some optimized brute-force solutions are also got accepted.

7

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.

8

@xellos0: Nice solution :slight_smile: 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.

1 Like
9

Here, the two key ideas are:

  1. Path-Substree Duality

How many nodes in the substree rooted at u? This is a sub-tree 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.

  1. Auxiliary Nodes

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.

5 Likes
10

@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 :frowning: http://www.codechef.com/viewsolution/3101164

11

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.

12

@mugurelionut: I never said your solution was a brute-force. :smiley:

13

It is my first time using HLD too, I am getting TLE though :confused: 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 :slight_smile:

Many thanks!

3 Likes
14

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?

15

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 :/)

1 Like
16

thank you for clearing my doubt.

17

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.

2 Likes
18

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.

19

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


20

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: