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.