You are not logged in. Please login at www.codechef.com to post your questions!

×

PRUNING - Editorial

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.

This question is marked "community wiki".

asked 26 Nov '12, 15:20

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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