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?