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.

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 188 |

3 | rng_58 | 185 |

3 | Errichto | 185 |

5 | SecondThread | 182 |

6 | Ashishgup | 175 |

6 | Um_nik | 175 |

8 | maroonrk | 174 |

9 | antontrygubO_o | 170 |

10 | -is-this-fft- | 169 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2021 08:02:25 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.What is order here?

Number of vertices in a graph.

""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.

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.

What's the logic also behind this :( Again this portion is not clear.

It'll be more clear if you draw a tree with nodes hanging from its diameter.

Thank you.

Ping me after you implement it. I'm not sure if this works, I didn't even try to implement it.

Got it :)