title: Dividing a graph in three parts such the maximum of the sum of weights of the three parts is minimized
body: <p>I want to divide a graph with N weighted-vertices and N-1 edges into three parts such that the maximum of the sum of weights of all the vertices in each of the parts is minimized. This is the actual problem i am trying to solve, <a href="http://www.iarcs.org.in/inoi/contests/jan2006/Advanced-1.php" rel="nofollow noreferrer">http://www.iarcs.org.in/inoi/contests/jan2006/Advanced-1.php</a></p>
  
  <p>I considered the following method </p>
  
  <pre><code>/*Edges are stored in an array E, and also in an adjacency matrix for depth first search.
  Every edge in E has two attributes a and b which are the nodes of the edge*/
  min-max = infinity
  for i -&gt; 0 to length(E):
     for j -&gt; i+1 to length(E):
       /*Call depth first search on the nodes of both the edges E[i] and E[j]
       the depth first search returns the sum of weights of the vertices it visits,
       we keep track of the maximum weight returned by dfs*/
       Adjacency-matrix[E[i].a][E[i].b] = 0;
       Adjacency-matrix[E[j].a][E[j].b] = 0;
       max = 0
       temp = dfs(E[i].a) 
       if temp &gt; max then max = temp
       temp = dfs(E[i].b) 
       if temp &gt; max then max = temp
       temp = dfs(E[i].a) 
       if temp &gt; max then max = temp
       temp = dfs(E[i].a) 
       if temp &gt; max then max = temp
  
       if max &lt; min-max
          min-max = max
       Adjacency-matrix[E[i].a][E[i].b] = 1;
       Adjacency-matrix[E[j].a][E[j].b] = 1;
      /*The depth first search is called four times but it will terminate one time
     if we keep track of the visited vertices because there are only three components*/
  
    /*After the outer loop terminates what we have in min-max will be the answer*/
  </code></pre>
  
  <p>The above algorithm takes O(n^3) time, as the number of edges will be n-1 the outer loop will run (n-1)! times that takes O(n^2) the dfs will visit each vertex only one so that is O(n) time.</p>
  
  <p>But the problem is that n can be &lt;= 3000 and O(n^3) time is not good for this problem. Is there any other method which will calculate the solve the question in the link faster than n^3?</p>
  
  <p><h3>EDIT:</h3> I implemented @BorisStrandjev's algorithm in c, it gave me a correct answer for the test input in the question, but for all other test inputs it gives a wrong answer, here is a link to my code in ideone <a href="http://ideone.com/67GSa2" rel="nofollow noreferrer">http://ideone.com/67GSa2</a>, the output here should be 390 but the program prints 395.</p>
  
  <p>I am trying to find if i have made any mistake in my code but i dont see any. Can anyone please help me here the answers my code gave are very close to the correct answer so is there anything more to the algorithm? </p>
  
  <p><h3>EDIT 2: </h3> In the following graph-</p>
  
  <p><img src="https://i.stack.imgur.com/jmnVJ.png" alt="enter image description here"> @BorisStrandjev, your algorithm will chose i as 1, j as 2 in one of the iterations, but then the third part (3,4) is invalid.</p>
  
  <h2>EDIT 3</h2>
  
  <p>I finally got the mistake in my code, instead of V[i] storing sum of i and all its descendants it stored V[i] and its ancestors, otherwise it would solve the above example correctly, thanks to all of you for your help. </p>