### wretched's blog

By wretched, history, 4 months ago,

I can findout the farthest nodes of a tree using dfs or bfs.How can I solve this problem using these technique or anything is new to solve this problem? Problem link : https://lightoj.com/problem/visiting-islands Help plz.

• +6

 » 4 months ago, # | ← Rev. 6 →   +3 Since, the graph may contain many trees. Find the diameter $d_i$ and order $o_i$ of each tree and pair them up {$d_i, o_i$} and sort them in decreasing diameter and order. And answer each query, if $k > max(o_i)$ then it's impossible and if $k \leq d_0$ then it's $k - 1$ else iterate through the pairs till $k \leq o_i$, then it's $d_i - 1 + 2(k - d_i)$.P.S. Precalculate the answers till $max(o_i)$ since the last condition might TLE.
•  » » 4 months ago, # ^ |   0 What is order here?
•  » » » 4 months ago, # ^ |   0 Number of vertices in a graph.
•  » » » » 4 months ago, # ^ |   0 ""else iterate through the pairs till k≤oi, then it's di−1+2(oi−k)."" This portion is not clear to me.Please make me clear. Thanks for your co-operation.
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 Oops! That's a blunder. I changed it to $d_i - 1 + 2(k - d_i)$ now since you have to pay $2(k - d_i)$ to visit $k - d_i$ islands before you visit the farthest node.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 What's the logic also behind this :( Again this portion is not clear.
•  » » » » » » » 4 months ago, # ^ |   0 It'll be more clear if you draw a tree with nodes hanging from its diameter.
•  » » » » » » » » 4 months ago, # ^ |   0 Thank you.
•  » » » » » » » » » 4 months ago, # ^ |   0 Ping me after you implement it. I'm not sure if this works, I didn't even try to implement it.
•  » » » » » » 4 months ago, # ^ |   0 Got it :)