back_slash's blog

Question on Tree
By back_slash, history, 5 years ago, In English

Given an undirected graph which is a tree with N nodes (N >= 3). You have to select an internal node (nodes with degree >= 2) and calculate the sum of the distance of all non-internal nodes (nodes with degree 1) from that node. You have to print the minimum possible value of the sum. And if possible also print the internal node number which gives you the minimum value. If there are multiple internal nodes which give the same minimum sum to all non-internal nodes print any of them. Can we solve this question in less than O(N^2) time complexity??

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by back_slash (previous revision, new revision, compare).

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

Auto comment: topic has been updated by back_slash (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Pre-calculate $$$f(v_{1}, v_{2})$$$ for all $$$(v_{1}, v_{2}) \in e$$$ where $$$f(v_{1}, v_{2}) = $$$ sum of all distances over edge $$$(v_{1}, v_{2})$$$ at $$$v_{1}$$$'s side.

→ Reply