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 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

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

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

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: Mar/05/2021 07:11:36 (i2).

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 :)