Hello, all! I am thinking about the following problem:
Given a tree with N vertices and some constant D. You are to find maximum number of vertices you can color if distance between any two colored vertices should be at least D.
How to solve this problem better than $$$O(N^2)$$$? I think for $$$O(N^2)$$$ we can use greedy approach; choose the farthest available vertex from the root.
Any helps are appreciated.
Very nice problem. Your greedy is correct and that can be used for $$$O(n\cdot\sqrt{n})$$$ solution.
Firstly, let's think about "brute-force" solution. Sort all vertices for its depth from root in descending order. Then iterate these vertices and if current vertex is available then increment the answer and start dfs from that vertex. dfs may go at most $$$O(n)$$$ vertices and we do dfs for each "answer vertex". Notice that answer can be at most $$$O(\frac{n}{d})$$$. So, overall complexity is $$$O(\frac{n^2}{d})$$$.
Now, the tricky part. If we use two dimensional used array such that used[v][d] means we are currently in the vertex v and we will go d more vertices; then we can stop if used[v][d] is already true in the dfs. So, the complexity becomes $$$O(n\cdot d)$$$.
Finally, we combine above solutions. If $$$d \leq \sqrt{n}$$$ then do the second, otherwise do the first one. It can be coded neatly with only one dfs.