### vkditya0997's blog

By vkditya0997, history, 4 years ago, Hello everyone,
I have seen many problems which can be solved using tree center.
So, I would like to know about it.
If someone can provide resources or explain it here in comments, It would be great!

and also my approach for today atCoder Problem C was something like this : ( failed! )

• Find an extreme of a diamemter of tree, This can be done by running a dfs from any arbitrary node. The node whose depth is highest is one of the extreme. ( Please correct me? )
• find the diameter from this extreme ( the highest depth from this node ).
• the nodes with the depth equal to the diameter are pushed into a vector ( let's say A ).
• Now, for every node in the vector A, Run a dfs and count the no of nodes having depth greater than K. the minimum of these would be the answer.

Where did I go wrong?  Comments (9)
 » Consider a graph 0 1 1 2 3 2 3 4 5 4 6 5 7 6 8 7 10 9 11 9 12 9 13 9 14 9 14 4 with K = 2. Now, the extreme diameter is 8 (between 0 and 8), but the optimal solution is to pick vertices 9-14, none of which even lies on the longest path.
 » In your second dfs, where you find the diameter using the extremal vertex, you should store the parents for every node. Then you can do this simple code to find the center after your dfs is finished: current = vertex_with_maximum_distance while dist[current] > diameter/2: current = parent[current] center = current