×

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.

This question is marked "community wiki".

19.8k350498541
accept rate: 36%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,359
×6
×6

question asked: 26 Nov '12, 15:20

question was seen: 1,191 times

last updated: 26 Nov '12, 15:20