title: Solution to 2010 ACM Problem: Castles
body: <p>Post your best solutions! You can find the full problem description and examples here: <a href="https://cm.baylor.edu/ICPCWiki/attach/Problem%20Resources/2010WorldFinalProblemSet.pdf" rel="nofollow noreferrer">ACM 2010 problems (pdf)</a></p>
  
  <p>You have a set of castles connected by roads, and you want to conquer all the castles with the minimum number of soldiers. Each castle has three properties: the minimum number of soldiers required to take it, the number of soldiers that will die taking it, and the number of soldiers that must be left behind to hold it.</p>
  
  <p>There is exactly one path between any two castles (the roads form a tree). You can pick any castle as the first target, but you must follow the roads afterward. You can only travel a road twice. Your mobile army must stay in one group.</p>