DP on tree Problem

Revision en1, by C21, 2019-09-20 02:58:41

Problem: https://www.codechef.com/problems/HLD/

I was only able to come up with the simple O(n^2) DP. I went through the editorial but didn't fully understand it.

Can someone share their ideas/approaches.

Any help would be appreciated.

Tags #dynamic programming, dp on a tree, dp optimisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English C21 2019-09-22 12:04:24 14
en2 English C21 2019-09-20 03:00:13 0 (published)
en1 English C21 2019-09-20 02:58:41 264 Initial revision (saved to drafts)