title: Node-weighted DAGs and longest paths with updates
body: <p>Suppose you have a set of jobs which can possibly be done in parallel. Each job has a time requirement ( time requirement for the i th job is t_i ). There are also some dependencies, the i th of them saying that you have to do job u_i before job v_i. You have to minimize the total time required.</p>
  
  <p>This is easily done by converting these relations into a directed acyclic graph and then using it to determine which ones to do in parallel. </p>
  
  <p>In case I'm not clear, here is an example. Suppose you have 5 jobs with time requirements 2, 9, 3, 12, 5, and you have to do 3 before 5, 4 before 5, 3 before 1 and 1 before 2. Then the best you can do is 17. This is your dag:</p>
  
  <pre><code>+---&gt; 1 (2) ---&gt; 2(9)
  |
  3 (3)
  |
  +----&gt; 5 (5)
         ^
         |
  4 (12)-+
  </code></pre>
  
  <p>You can do 3 and 4 in parallel, so that you spend MAX(3,12)=12 units of time before doing 5, which takes 5 units of time. So 5 is completed after 17 units of time. On the other hand 2 is completed after 14 units. So the answer is 17.</p>
  
  <p>The question is, if exactly one time requirement in updated in each query (where everytime you start with the original graph, not the graph resulting after the previous modifications)
  how can you efficiently find the new minimum time requirement?</p>
  
  <p>For those who want constraints, number of jobs &lt;= 10^5. number of dependencies &lt;= 10^6, number of queries &lt;= 10^6.</p>