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?
Someone please help me?
Thanks in Advance
Consider a graph
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.
There is a very nice and easy to implement algorithm for finding center of a tree.
1) Push all the leaves in a queue.
2) Remove the top element and remove the edges , if new leaves form push in queue.
3) The last node to be pushed in the queue is the Center
Doesn't work for all graphs, only for trees.
Yeah by mistake I wrote graph.
What all things can be done by finding the center of a tree? Can you give one or two applications?
Popular example might be Problem ( I am not sure though as I haven't solved it but I have heard it can be solved by finding absolute center ) .
Other problems generally ask directly for center after updates. I haven't really seen much problems on center.
From what I've understood this will find a center, not necessarily all centers (i.e, if there exists a second). Can this algorithm be applied in a way that finds all centers?
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: