You are not logged in. Please login at www.codechef.com to post your questions!

×

QTREE6 - Editorial

5
6

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

alt text

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.

This question is marked "community wiki".

asked 16 Dec '13, 18:53

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446375
accept rate: 0%

edited 26 Dec '13, 15:06

admin's gravatar image

0★admin ♦♦
19.6k349497539

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

(21 Dec '13, 08:12) hatim0093★

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

(22 Dec '13, 18:37) hatim0093★

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

(24 Dec '13, 14:28) jalaj52973★

What is segment cover operation?

(30 Dec '13, 14:24) jaskaran_13★

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.

link

answered 17 Dec '13, 03:14

xiaodao's gravatar image

5★xiaodao
19635
accept rate: 0%

edited 17 Dec '13, 03:55

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

link

answered 16 Dec '13, 20:14

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

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

(16 Dec '13, 20:33) shangjingbo ♦♦3★
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 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.

(16 Dec '13, 21:39) mugurelionut7★

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

(17 Dec '13, 03:18) xiaodao5★

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

(17 Dec '13, 10:12) shangjingbo ♦♦3★

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!

link

answered 18 Dec '13, 02:19

brunoja's gravatar image

6★brunoja
764
accept rate: 0%

edited 19 Dec '13, 03:50

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

(20 Dec '13, 10:49) hatim0093★

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) brunoja6★

did u used 2-D BIT for this?

(20 Dec '13, 22:34) hatim0093★

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) hatim0093★

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

(21 Dec '13, 18:16) brunoja6★

@brunoja what is the inverse array used for?

(29 Dec '13, 02:56) jaskaran_13★
showing 5 of 6 show all

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

link

answered 16 Dec '13, 19:39

yashkumar18's gravatar image

5★yashkumar18
82661224
accept rate: 18%

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.

(16 Dec '13, 20:32) shangjingbo ♦♦3★

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.

link

answered 16 Dec '13, 20:32

sanchit_h's gravatar image

6★sanchit_h
24617
accept rate: 0%

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.

(16 Dec '13, 20:56) shangjingbo ♦♦3★

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.

link

answered 17 Dec '13, 06:15

samjay's gravatar image

5★samjay
4271510
accept rate: 10%

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) devanshdalal4★
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) brunoja6★

thank you for clearing my doubt.

(18 Dec '13, 19:36) devanshdalal4★
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) samjay5★

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.

link

answered 20 Dec '13, 08:07

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

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(c) > size(v)/2, it means that size(c) 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 :)

(20 Dec '13, 18:57) brunoja6★

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.

(20 Dec '13, 22:15) hatim0093★

You can choose ties in any way.

(08 Jan '14, 19:50) shangjingbo ♦♦3★

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

link

answered 24 Dec '13, 16:11

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

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

link

answered 26 Dec '13, 14:39

hatim009's gravatar image

3★hatim009
46421122
accept rate: 8%

edited 30 Dec '13, 12:47

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

link

answered 30 Dec '13, 14:47

jaskaran_1's gravatar image

3★jaskaran_1
525233550
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,182
×1,321
×52
×16
×15

question asked: 16 Dec '13, 18:53

question was seen: 13,323 times

last updated: 06 Jun '15, 17:49