surajkvm007's blog

Graph theory problem

By surajkvm007, history, 8 years ago, In English

Given a forest with n vertices, add edges to make it into a tree with minimal diameter. I tried many approaches but none of them passed system test cases.Please suggest some algorithm to solve this problem.

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The idea is to play with tree diameters while merging trees, you can use the ideas in the editorial for this problem (is very similar): http://codeforces.com/contest/455/problem/C

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you link the problem?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

check the IOI 2013 Dreaming solution, it is almost the same problem.

→ Reply