infinitepro's blog

Direct edges of a tree to maximise pairs of reachable nodes
By infinitepro, history, 4 years ago, In English

The title states the problem — source. Constraints $$$N \le 25e4$$$

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Downvoters care to explain whats wrong?

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply