Why this algorithm is correct?

Revision en5, by 2016gdgzoi471, 2018-12-22 05:15:55

There are many ways to solve this problem, the problem E in round 514. My code was accepted, but can anyone give me a proof of my algorithm?
The process of my algorithm:
1.Find the vertex u with the maximum depth.
2.If this vertex has been covered, ignore it and goto 1.
3.Find another vertex v with the minimum depth. It is an ancestor of u, and the sum of w of all the vertexes on the path between u and v does not exceed S.
4.Cover all the vertexes between u and v.
5.If there are still uncovered vertexes, goto 1.
Can anyone give me a proof of my algorithm?

Tags greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English 2016gdgzoi471 2018-12-22 05:15:55 8 Tiny change: 'roblem/E),the proble' -> 'roblem/E), the proble'
en4 English 2016gdgzoi471 2018-12-22 05:14:38 1 Tiny change: 'roblem/E),the proble' -> 'roblem/E), the proble'
en3 English 2016gdgzoi471 2018-12-22 05:14:19 19 Tiny change: 'problem/E) problem. My code ' -> 'problem/E),the problem E in round 514. My code '
en2 English 2016gdgzoi471 2018-12-22 05:13:30 16
en1 English 2016gdgzoi471 2018-12-22 05:13:07 621 Initial revision (published)