case class Edge(to: Int, cost: Int) object Main extends App { val scan = new java.util.Scanner(System.in) val n, m = scan.next().toInt val points = (1 to n).toArray.map(_ => scan.next().toInt) val edges: Array[List[Edge]] = Array.fill(n)(List()) for (_ <- 1 until n) { val from, to, cost = scan.next().toInt edges(from) = Edge(to, cost) :: edges(from) edges(to) = Edge(from, cost) :: edges(to) } val memo: Array[Array[Int]] = Array.fill(n, m+1)(0) dfs(0, -1) println(memo(0).max) def dfs(cur: Int, prev: Int) { for (i <- 0 to m) memo(cur)(i) = points(cur) for (edge <- edges(cur); if prev != edge.to) { dfs(edge.to, cur) for (i <- m to 0 by -1; j <- i+edge.cost*2 to 0 by -1) { if (i-(j+edge.cost*2) >= 0) { memo(cur)(i) = math.max( memo(cur)(i), memo(cur)(i-(j+edge.cost*2)) + memo(edge.to)(j)) } } } } }