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