During a lot of algorithm competitions I met colored tree questions and there have been multiple cases where I though of different approaches. I'm curious what is the best way of solving the following problem:

Given a tree with N nodes: 2 <= N <= 100 000. Every node has a color c : 2 <= c <= 100 000. You are supposed answer Q queries 2 <= Q <= 100 000. There are 2 types of queries:

  1. what is the closest ancestor of node V that has same color as V
  2. change the color of node V to other color (possible not existing in the set of already used colors).

Obviously the brute force solution O(N) for a query is not accepted. I assume that there is a way of having a query solved in Log(N) or Log(N)^2.

From what I have searched this looks like the "Marked Ancestor Problem" but I can't find something good to read.

Thank you in advance.

  • $\begingroup$ What approaches have you considered? You might just need to spend more time brainstorming possible ideas. We're happy to help you understand the concepts but just solving exercises / competition problems for you is unlikely to achieve that. You might find this page helpful in improving your question. Also, you might want to edit your question to improve its formatting. $\endgroup$ – D.W. Jun 29 '17 at 20:55
  • $\begingroup$ Sorry @D.W. This is not a an exercise or a competition problem (I'm not in school for quite some time now - I just try to learn new algorithms via different competitions online - usually link. While I was solving different problems I have thought of this problem. Regarding the formatting please excuse me - this is the first question posted here since most of the time I use the competitions internal blogs, but since this is an external problem I tried to found the right place to ask this. A quick search on Google showed that this is the "algorithm guru questions". $\endgroup$ – Florian Mocanu Jun 30 '17 at 5:47
  • $\begingroup$ Regarding the approach I was thinking -> for every node while doing a dfs maintain a persistent trie for every color. For the first type of question I would simply query the closest left leaf of the current node's leaf (if exists). For the second type of query I'm supposed to erase a node from persistent trie and find the place where to add this, but here I got stuck. $\endgroup$ – Florian Mocanu Jun 30 '17 at 5:48
  • $\begingroup$ should I post the questions in another place ? $\endgroup$ – Florian Mocanu Jul 1 '17 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.