There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries:
- Set(X): change the given vertex X from type 0 to type 1,
- Dist(X): find the shortest path from X to a node of type 1 and return the length of this path. This will return zero if X is of type 1.
The naive method would be to just maintain a tree and on every update change the type of vertex; to answer queries of second type, run a bfs starting at X and stop as soon as a vertex with type 1 is found. With this simple scheme, Set(X) would run in $O(1)$ time, but Dist(X) would take $O(n)$ time.
However, in my application the number of queries and number of nodes are both of the order of $10^5$, so the naive method is too slow. In particular, $O(n)$ time is too slow.
Can somebody suggest a better algorithm for doing this?