### infinitepro's blog

By infinitepro, history, 3 years ago,

The title states the problem — source. Constraints

Unable to parse markup [type=CF_MATHJAX]

• +20

 » 3 years ago, # |   -9 Downvoters care to explain whats wrong?
 » 3 years ago, # |   +11 Looks like a copy of this problem. The solution is to work with the centroid of the tree. All edges must go either towards the centroid or away from the centroid. In other words, there is an optimal solution where for any arbitrary node $u$ and centroid $c$, it is possible to reach $u$ from $c$ or $c$ from $u$. So the solution boils down to doing a knapsack problem on the subtree sizes of the tree rooted at the centroid.Don't ask me for the proof, because I do not know it :3, I only know the solution because it is a very popular problem of POI.
•  » » 3 years ago, # ^ |   0 Many thanks for the reference! I tried translating the editorial https://oi.edu.pl/static/attachment/20140306/oi20.pdf (page 158) but I wasn't able to deduce the proof for why this approach is optimal.