PROBLEM LINKSDIFFICULTYHARD EXPLANATIONThis 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).
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
SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 26 Nov '12, 15:20
