PRUNING - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

HARD

EXPLANATION

This can be solved with dynamic programming. Let w(u,v) denote the weight of the edge between u and v. Root the tree at an arbitrary node r. For nodes v,c within distance d of each other, let m(v,c) denote the maximum total weight of edges in the subtree rooted at v among all solutions that have c being the center of the component containing v. Then m(v,c) satisfies the following recurrence. To simplify notation, let k(u) denote the maximum over all m(u,c) where c ranges over nodes in the subtree rooted at u whose distance to u is at most d (i.e. not considering possible centers c that are not included in the subtree rooted at u).

  • if v is a leaf, then m(v,c) = 0
  • if v is not a leaf and either c = v or the path from v to c goes through the parent of v, then m(v,c) is the sum, over all children u of v, of the quantities

  1. max(k(u), m(u,c) + w(u,v)) if the distance from u to c is at most d

  2. k(u) if the distance from u to c exceeds d

  • if v is not a leaf and c is in a subtree rooted at some child u’ of v, then m(v,c) is the sum of w(u’,v) + m(u’, c) plus the sum, overall children u != u’ of v, of the quantities listed in the previous point.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like