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.