Hello,
I 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. There are 2 types of queries:
- what is the closest ancestor of node V that has same color as V
- 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) 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 something good to read.
Thank you in advance.
1 Like
Why wouldn’t brute force be accepted? Worst case complexity is O(N*Q) which is ~10^7 operations. Run-time would be <1 sec.
1 Like
I believe brute force should work since Q is small. Aside from that, I think on the top of my head for the optimal solution, you can use Heavy-Light Decomposition with a Merge Sort Tree per chain.
You can lookup the closest ancestor by climbing the HLD chains, and checking the merge sort tree if the current color exists. For update, you can simply do point update on the merge sort tree. That will result in total of O(log^3 N) complexity, or if implemented in another way such as using hash maps can be reduced to amortized O(log^2 N) per query.
1 Like
Sorry, my mistake - Q <= 100 000.
Sorry, my mistake - Q <= 100 000.
Thanks for the idea. I will try to implement and see some time results for random queries.
