AtomRush's blog

Wunder fund : Problem D . Dp solution
By AtomRush, history, 9 years ago, In English

Problem LINK I am not able to understand the DP solution of this problem.What does the state represent ? Some solution Links using this DP First Second Third

Tags dp
  • Vote: I like it
  • -9
  • Vote: I do not like it

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

HELP

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this was asked a week ago. The OP perhaps deleted the thread, cannot find it now.

The 2 states are (It's a tree DP, so for each vertex i, we consider only its subtrees and itself):

  1. Maximum number of edges with the vertex not "full" (ie. connected to no more than 1 vertex, the vertex can still connect to the parent).
  2. Maximum number of edges with the vertex "full" (ie. connected to 2 vertices already).
→ Reply